fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MAX_INT 2147483647
  3. #define MAX_LONG 9223372036854775807ll
  4. #define MAX_ULONG 18446744073709551615ull
  5. #define MAX_DBL 1.7976931348623158e+308
  6. #define EPS 1e-9
  7. const double PI = 2.0*acos(0.0);
  8.  
  9. #define INF 1000000000
  10.  
  11. using namespace std;
  12. typedef long long ll;
  13. typedef pair<int, int> ii;
  14.  
  15.  // swapped the array limits here as we make sure m < n
  16. int m, n, k, city[1005][30005], x, y, r, b, dis[1005], ans[1000005];
  17.  
  18. void update_ranges() {
  19.         int i, j, r2 = r*r, lim;
  20.         city[y][(x-r) >= 1 ? x-r : 1] += b;
  21.         if (x+r+1 <= n) city[y][x+r+1] -= b;
  22.  
  23.        	// only compute necessary square roots
  24.         lim = min(r-1, max(y-1, m-y));
  25.         for (i=1, j=0; i<=lim; i++, j++)
  26.                 dis[j] = (int) sqrt(r2-i*i);
  27.  
  28.         lim = min(m, y+r-1);
  29.         for (i=y+1, j=0; i<=lim; i++, j++) {
  30.                 city[i][(x-dis[j]) >= 1 ? x-dis[j] : 1] += b;
  31.                 if (x+dis[j]+1 <= n) city[i][x+dis[j]+1] -= b;
  32.         }
  33.         if ((y+r) <= m) {
  34.                 city[y+r][x] += b;
  35.                 if (x < n) city[y+r][x+1] -= b;
  36.         }
  37.         lim = max(0, y-r+1);
  38.         for (i=y-1, j=0; i>=lim; i--, j++) {
  39.                 city[i][(x-dis[j]) >= 1 ? x-dis[j] : 1] += b;
  40.                 if (x+dis[j]+1 <= n) city[i][x+dis[j]+1] -= b;
  41.         }
  42.         if ((y-r) >= 1) {
  43.                 city[y-r][x] += b;
  44.                 if (x < n) city[y-r][x+1] -= b;
  45.         }
  46. }
  47.  
  48. int main () {
  49.         ios_base::sync_with_stdio(0);
  50.         int i, j;
  51.  
  52.         scanf("%d", &m);
  53.         scanf("%d", &n);
  54.         scanf("%d", &k);
  55.  
  56.         // we swap x and y if m >= n, because this way we get K * min(m,n) operations 
  57.         // in the update_ranges() function instead of K * m operations
  58.         bool swapped = false;
  59.         if (m > n) {
  60.         	swap(m,n);
  61.         	swapped = true;
  62.         }
  63.  
  64.         for (i=0; i<k; i++) {
  65.                 scanf("%d %d %d %d", &x, &y, &r, &b);
  66.                 if (swapped) swap(y,x);
  67.                 update_ranges();
  68.         }
  69.  
  70.         for (i=1; i<=m; i++)
  71.                 for (j=1; j<=n; j++)
  72.                         ans[city[i][j] += city[i][j-1]]++;
  73.  
  74.         for (i=1000005; ans[i]==0; i--);
  75.  
  76.         printf("%d\n%d\n", i, ans[i]);
  77.  
  78.         return 0;
  79. }
Success #stdin #stdout 0s 125120KB
comments (?)
stdin
copy 
3
5
3
1 3 2 5
3 1 2 7
5 1 1 5
stdout
copy 
12
5
https://ideone.com/6GKB8Z
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!