Submission #142692

#TimeUsernameProblemLanguageResultExecution timeMemory
142692lycNuclearia (CEOI15_nuclearia)C++14
25 / 100
726 ms111540 KiB
//#define DEBUG #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef pair<ii, int> ri3; #define mp make_pair #define pb push_back #define fi first #define sc second #define SZ(x) (int)(x).size() #define ALL(x) begin(x), end(x) #define REP(i, n) for (int i = 0; i < n; ++i) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define RFOR(i, a, b) for (int i = a; i >= b; --i) #ifdef DEBUG #define DBG(...) __VA_ARGS__ #else #define DBG(...) #endif const int MAXN = 2e5+5; const int MAXWH = 3000000; int W,H,N,Q; struct Plant { int x, y, a, b; }; struct NUCLEARIA { ll data[MAXWH]; inline ll& operator() (int x, int y) { return data[(y*(W+1)) + x]; } } nuclearia, posDiag, negDiag, row, col; inline void addSquare(int sx, int sy, int ex, int ey, ll c) { sx = max(1, sx); sy = max(1, sy); nuclearia(sx , sy ) += c; if (ex+1 <= W) nuclearia(ex+1, sy ) -= c; if (ey+1 <= H) nuclearia(sx , ey+1) -= c; if (ex+1 <= W and ey+1 <= H) nuclearia(ex+1, ey+1) += c; } inline void addCol(int x, int sy, int ey, ll m) { col(x,sy) += m; if (ey+1 <= H) col(x,ey+1) -= m; } inline void addRow(int y, int sx, int ex, ll m) { row(sx,y) += m; if (ex+1 <= W) row(ex+1,y) -= m; } inline void addNegDiag(int sx, int sy, int ex, int ey, ll m) { DBG(cout << "ADD NEG " << sx << " " << sy << " TO " << ex << " " << ey << " BY " << m << endl;) if (sx < 1 and sy < 1) { int out = max(1-sx, 1-sy); nuclearia(1,1) += (ll) out * m; sx += out, sy += out; } else if (sx < 1) { int out = 1-sx; addCol(1,sy,sy+out-1,m); sx += out, sy += out; } else if (sy < 1) { int out = 1-sy; addRow(1,sx,sx+out-1,m); sx += out, sy += out; } negDiag(sx, sy) += m; if (ex+1 <= W and ey+1 <= H) negDiag(ex+1, ey+1) -= m; } inline void addPosDiag(int sx, int sy, int ex, int ey, ll m) { DBG(cout << "ADD POS " << sx << " " << sy << " TO " << ex << " " << ey << " BY " << m << endl;) if (sx < 1 and sy > H) { int out = max(1-sx, sy-H); sx += out, sy -= out; } else if (sx < 1) { int out = 1-sx; addCol(1,sy-out+1,sy,m); sx += out, sy -= out; } else if (sy > H) { int out = sy-H; sx += out, sy -= out; } if (ex > W and ey < 1) { int out = max(ex-W, 1-ey); ex -= out, ey += out; } else if (ex > W) { int out = ex-W; ex -= out, ey += out; } else if (ey < 1) { int out = 1-ey; addRow(1,ex-out+1,ex,m); ex -= out, ey += out; } posDiag(sx, sy) += m; if (ex+1 <= W and ey-1 >= 1) posDiag(ex+1, max(1,ey-1)) -= m; } inline void summariseDiags() { FOR(x,1,W) FOR(y,1,H) { negDiag(x,y) += negDiag(x-1,y-1); posDiag(x,y) += posDiag(x-1,y+1); } //DBG(cout << "NEG DIAG " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << negDiag(x,y) << ' '; } cout << endl; }); //DBG(cout << "POS DIAG " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << posDiag(x,y) << ' '; } cout << endl; }); } inline void addDiags() { FOR(x,1,W) FOR(y,1,H) { nuclearia(x,y) += negDiag(x,y) + posDiag(x,y); } } inline void summariseLines() { FOR(x,1,W) FOR(y,1,H) { row(x,y) += row(x-1,y); col(x,y) += col(x,y-1); } //DBG(cout << "ROW " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << row(x,y) << ' '; } cout << endl; }); //DBG(cout << "COL " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << col(x,y) << ' '; } cout << endl; }); } inline void addLines() { FOR(x,1,W) FOR(y,1,H) { nuclearia(x,y) += row(x,y) + col(x,y); } } inline void summarise() { FOR(x,1,W) FOR(y,1,H) { //col(x,y) += col(x,y-1); nuclearia(x, y) += nuclearia(x-1, y) + nuclearia(x, y-1) - nuclearia(x-1, y-1); } DBG(cout << "NUCLEARIA " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << setw(2) << nuclearia(x, y) << ' '; } cout << endl; }); } int main() { //freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); cin >> W >> H; cin >> N; Plant plant[N]; FOR(i,0,N-1) { int x,y,a,b; cin >> x >> y >> a >> b; plant[i] = {x,y,a,b}; } for (Plant p : plant) { int r = (p.a-1)/p.b; DBG(cout << "PLANT " << p.x << " " << p.y << " a b " << p.a << " " << p.b << " r " << r << endl;) addSquare(p.x-r, p.y-r, p.x+r, p.y+r, p.a % p.b); // add directly to nuclearia_aux if (p.a % p.b == 0) ++r; if (r > 0) { addNegDiag(p.x-r+1, p.y-r+1, p.x+r , p.y+r , p.b); addPosDiag(p.x-r+1, p.y+r , p.x+r , p.y-r+1, -p.b); } } summariseDiags(); addDiags(); // add to nuclearia_aux summariseLines(); addLines(); // add to nuclearia_aux DBG(cout << "AUX " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << nuclearia(x,y) << ' '; } cout << endl; }) summarise(); // calc nuclearia summarise(); // calc nuclearia_pre cin >> Q; FOR(q,0,Q-1) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; ll s = nuclearia(x2,y2) - nuclearia(x1-1,y2) - nuclearia(x2,y1-1) + nuclearia(x1-1,y1-1); ll r = (ll)(x2-x1+1)*(y2-y1+1); cout << (ll)round((long double)s/r) << '\n'; } }
#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...