Submission #39497

#TimeUsernameProblemLanguageResultExecution timeMemory
39497funcsrNuclearia (CEOI15_nuclearia)C++14
30 / 100
766 ms99812 KiB
#include <iostream> #include <vector> #include <set> #include <algorithm> #include <cassert> using namespace std; #define rep(i, n) for (int i=0; i<(n); i++) #define pb push_back #define all(x) x.begin(), x.end() #define uniq(x) x.erase(unique(all(x)), x.end()) inline int abs(int x) { if (x < 0) return -x; return x; } int W, H, N, Q; long long A[2500000]; inline int p(int x, int y) { return y*W+x; } vector<long long> B[2500000]; int main() { scanf("%d %d %d", &W, &H, &N); assert(W*H*N <= 1e8); if (H > 1) { rep(x, W) B[x].resize(H, 0); rep(i, N) { int x, y, a, b; scanf("%d %d %d %d", &x, &y, &a, &b); x--, y--; rep(xx, W) rep(yy, H) { int dist = max(abs(xx-x), abs(y-yy)); B[xx][yy] += max(0LL, a-1LL*b*dist); } } rep(y, H) rep(x, W-1) B[x+1][y] += B[x][y]; rep(y, H-1) rep(x, W) B[x][y+1] += B[x][y]; scanf("%d", &Q); rep(i, Q) { int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); x1--, y1--, x2--, y2--; long long s = B[x2][y2]; if (x1 > 0) s -= B[x1-1][y2]; if (y1 > 0) s -= B[x2][y1-1]; if (x1 > 0 && y1 > 0) s += B[x1-1][y1-1]; long long q = 1LL*(x2-x1+1)*(y2-y1+1); //cout<<s<<"/"<<q<<"\n"; printf("%lld\n", ((2LL*s/q)+1)/2); } } else { //cout<<"W="<<W<<",H="<<H<<", N="<<N<<"\n"; rep(i, N) { int x, y, a, b; scanf("%d %d %d %d", &x, &y, &a, &b); x--, y--; rep(xx, W) rep(yy, H) { int dist = max(abs(xx-x), abs(y-yy)); A[p(xx, yy)] += max(0LL, a-1LL*b*dist); } } rep(y, H) rep(x, W-1) A[p(x+1, y)] += A[p(x, y)]; rep(y, H-1) rep(x, W) A[p(x, y+1)] += A[p(x, y)]; scanf("%d", &Q); rep(i, Q) { int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); x1--, y1--, x2--, y2--; long long s = A[p(x2, y2)]; if (x1 > 0) s -= A[p(x1-1, y2)]; if (y1 > 0) s -= A[p(x2, y1-1)]; if (x1 > 0 && y1 > 0) s += A[p(x1-1, y1-1)]; long long q = 1LL*(x2-x1+1)*(y2-y1+1); //cout<<s<<"/"<<q<<"\n"; printf("%lld\n", ((2LL*s/q)+1)/2); } } return 0; }

Compilation message (stderr)

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:23:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &W, &H, &N);
                                ^
nuclearia.cpp:29:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d", &x, &y, &a, &b);
                                           ^
nuclearia.cpp:38:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
                    ^
nuclearia.cpp:41:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                                               ^
nuclearia.cpp:56:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d", &x, &y, &a, &b);
                                           ^
nuclearia.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &Q);
                    ^
nuclearia.cpp:68:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...