제출 #142544

#제출 시각아이디문제언어결과실행 시간메모리
142544lycNuclearia (CEOI15_nuclearia)C++14
0 / 100
1107 ms776712 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) const int MAXN = 2e5+5; int W,H,N,Q; bool flag; struct Plant { int x, y, a, b; }; struct Data { ll ldmx, ldmy, ldc, rdmx, rdmy, rdc, rmx, rmy, rc, cmx, cmy, cc, v; }; #ifdef DEBUG #define DBG(...) __VA_ARGS__ #else #define DBG(...) #endif 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}; } Data g[W+2][H+2]; memset(g, 0, sizeof g); for (Plant p : plant) { int r = (p.a+p.b-1)/p.b - 1; // i: [1 to r] :: [y-r, y-i-1], [y-i,y+i], [y+i+1,y+r] //p.a - (p.y-y)*p.b //= y*p.b - p.y*p.b + p.a // u g[max(1,p.x-r)][max(1,p.y-r)].rmy += p.b; g[max(1,p.x-r)][max(1,p.y-r)].rc += - p.y*p.b + p.a; g[min(W,p.x+r)+1][max(1,p.y-r)].rmy -= p.b; g[min(W,p.x+r)+1][max(1,p.y-r)].rc -= - p.y*p.b + p.a; //p.a - (y-p.y)*p.b //= y*(-p.b) + p.y*p.b + p.a // d g[max(1,p.x-r)][min(H,p.y+r)+1].rmy -= - p.b; g[max(1,p.x-r)][min(H,p.y+r)+1].rc -= p.y*p.b + p.a; g[min(W,p.x+r)+1][min(H,p.y+r)+1].rmy += - p.b; g[min(W,p.x+r)+1][min(H,p.y+r)+1].rc += p.y*p.b + p.a; int x,y; //p.a - (p.x-x)*p.b //= x*p.b - p.x*p.b + p.a // ld x = p.x-r, y = p.y-r; if (x < 1 or y < 1) { int z = max(1-x, 1-y); int xp = x+z, yp = y+z; g[max(1,x)][yp].rmy -= p.b; g[max(1,x)][yp].rc -= - p.y*p.b + p.a; g[xp][yp].rmy += p.b; g[xp][yp].rc += - p.y*p.b + p.a; g[max(1,x)][yp].rmx += p.b; g[max(1,x)][yp].rc += - p.x*p.b + p.a; g[xp][yp].rmx -= p.b; g[xp][yp].rc -= - p.x*p.b + p.a; x = xp, y = yp; } g[x][y].ldmy -= p.b; g[x][y].ldc -= - p.y*p.b + p.a; g[p.x][p.y].ldmy += p.b; g[p.x][p.y].ldc += - p.y*p.b + p.a; g[x][y].ldmx += p.b; g[x][y].ldc += - p.x*p.b + p.a; g[p.x][p.y].ldmx -= p.b; g[p.x][p.y].ldc -= - p.x*p.b + p.a; // g[p.x][p.y].ldmy += - p.b; g[p.x][p.y].ldc += p.y*p.b + p.a; g[p.x][p.y].ldmx -= - p.b; g[p.x][p.y].ldc -= p.x*p.b + p.a; x = p.x+r, y = p.y+r; if (x > W or y > H) { int z = max(x-W, y-H); int xp = x-z, yp = y-z; g[xp+1][yp].rmy += - p.b; g[xp+1][yp].rc += p.y*p.b + p.a; g[min(W,x)+1][yp].rmy -= - p.b; g[min(W,x)+1][yp].rc -= p.y*p.b + p.a; g[xp][yp].rmx -= - p.b; g[xp][yp].rc -= p.x*p.b + p.a; g[min(W,x)+1][yp].rmx += - p.b; g[min(W,x)+1][yp].rc += p.x*p.b + p.a; x = xp, y = yp; } g[x+1][y+1].ldmy -= - p.b; g[x+1][y+1].ldc -= p.y*p.b + p.a; g[x+1][y+1].ldmx += - p.b; g[x+1][y+1].ldc += p.x*p.b + p.a; // rd x = p.x-r, y = p.y+r; DBG(cout << "UPDATE " << x << " " << y << " TO " << p.x << " " << p.y << endl;) if (x < 1 or y > H) { int z = max(1-x, y-H); int xp = x+z, yp = y-z; DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;) g[max(1,x)][yp].rmy += - p.b; g[max(1,x)][yp].rc += p.y*p.b + p.a; g[xp][yp].rmy -= - p.b; g[xp][yp].rc -= p.y*p.b + p.a; g[max(1,x)][yp].rmx -= p.b; g[max(1,x)][yp].rc -= - p.x*p.b + p.a; g[xp][yp].rmx += p.b; g[xp][yp].rc += - p.x*p.b + p.a; x = xp, y = yp; } g[x][y].rdmy += - p.b; g[x][y].rdc += p.y*p.b + p.a; g[p.x][p.y].rdmy -= - p.b; g[p.x][p.y].rdc -= p.y*p.b + p.a; g[x][y].rdmx -= p.b; g[x][y].rdc -= - p.x*p.b + p.a; g[p.x][p.y].rdmx += p.b; g[p.x][p.y].rdc += - p.x*p.b + p.a; // g[p.x][p.y].rdmy -= p.b; g[p.x][p.y].rdc -= - p.y*p.b + p.a; g[p.x][p.y].rdmx += - p.b; g[p.x][p.y].rdc += p.x*p.b + p.a; x = p.x+r, y = p.y-r; DBG(cout << "UPDATE " << p.x << " " << p.y << " TO " << x << " " << y << endl;) if (x > W or y < 1) { int z = max(x-W, 1-y); int xp = x-z, yp = y+z; DBG(cout << " CONVERT X Y TO P " << xp << " " << yp << endl;) DBG(cout << " RANGE " << xp+1 << " TO " << min(W,x)+1 << " AT " << yp << endl;) g[xp+1][yp].rmy -= p.b; g[xp+1][yp].rc -= - p.y*p.b + p.a; g[min(W,x)+1][yp].rmy += p.b; g[min(W,x)+1][yp].rc += - p.y*p.b + p.a; g[xp+1][yp].rmx += - p.b; g[xp+1][yp].rc += p.x*p.b + p.a; g[min(W,x)+1][yp].rmx -= - p.b; g[min(W,x)+1][yp].rc -= p.x*p.b + p.a; x = xp, y = yp; } DBG(cout << " MAIN " << x+1 << " " << y-1 << endl;) g[x+1][y-1].rdmy += p.b; g[x+1][y-1].rdc += - p.y*p.b + p.a; g[x+1][y-1].rdmx -= - p.b; g[x+1][y-1].rdc -= p.x*p.b + p.a; //break; } FOR(x,1,W) FOR(y,1,H) { g[x][y].rmx += g[x-1][y].rmx; g[x][y].rmy += g[x-1][y].rmy; g[x][y].rc += g[x-1][y].rc; g[x][y].ldmx += g[x-1][y-1].ldmx; g[x][y].ldmy += g[x-1][y-1].ldmy; g[x][y].ldc += g[x-1][y-1].ldc; g[x][y].rdmx += g[x-1][y+1].rdmx; g[x][y].rdmy += g[x-1][y+1].rdmy; g[x][y].rdc += g[x-1][y+1].rdc; g[x][y].cmx = g[x][y-1].cmx + g[x][y].ldmx + g[x][y].rdmx + g[x][y].rmx; g[x][y].cmy = g[x][y-1].cmy + g[x][y].ldmy + g[x][y].rdmy + g[x][y].rmy; g[x][y].cc = g[x][y-1].cc + g[x][y].ldc + g[x][y].rdc + g[x][y].rc; g[x][y].v = g[x][y].cmx * x + g[x][y].cmy * y + g[x][y].cc; g[x][y].v += g[x-1][y].v + g[x][y-1].v - g[x-1][y-1].v; } DBG( cout << "END " << endl; //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmx << ' '; } cout << endl; } cout << endl; //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rmy << ' '; } cout << endl; } cout << endl; //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].rc << ' '; } cout << endl; } cout << endl; //FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmx << ' '; } cout << endl; } cout << endl; ///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cmy << ' '; } cout << endl; } cout << endl; ///FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].cc << ' '; } cout << endl; } cout << endl; cout << "V " << endl; FOR(y,1,H) { FOR(x,1,W) { cout << g[x][y].v << ' '; } cout << endl; } cout << endl; ) cin >> Q; FOR(q,0,Q-1) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; ll s = g[x2][y2].v - g[x1-1][y2].v + g[x1-1][y1-1].v - g[x2][y1-1].v; ll r = (ll)(x2-x1+1)*(y2-y1+1); DBG(cout << "S R " << s << " " << r << endl;) 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...