Submission #139108

#TimeUsernameProblemLanguageResultExecution timeMemory
139108lycNuclearia (CEOI15_nuclearia)C++14
30 / 100
1065 ms183456 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; }; #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; flag = (W>H); if (flag) swap(W,H); cin >> N; Plant plant[N]; FOR(i,0,N-1) { int x,y,a,b; cin >> x >> y >> a >> b; if (flag) swap(x,y); plant[i] = {x,y,a,b}; } sort(plant,plant+N,[](Plant a, Plant b) { return a.x < b.x; }); ll m[W+2][H+2], c[W+2][H+2], v[W+2][H+2]; memset(m, 0, sizeof m); memset(c, 0, sizeof c); memset(v, 0, sizeof v); //int idx = 0; for (Plant p : plant) { //if (idx++ != 1) continue; int r = (p.a + p.b - 1) / p.b - 1; DBG(cout << "PLANT " << p.x << " " << p.y << " :: r " << r << endl;) FOR(i,0,r) if (p.x-r+i >= 1) { int ry = r-i; int ca = p.a - p.b * (r - i); DBG(cout << "PROCESS COL " << p.x-r+i << " :: ry " << ry << endl;) //ca - b*((p.y - ry) - y) = ca - b*p.y + b*ry + b*y DBG(cout << "SEG " << max(1,p.y-r) << " " << max(1,p.y-ry) << " " << min(H,p.y+ry+1) << " " << min(H,p.y+r+1) << endl;) DBG(cout << "\t\tVAR c " << ca - p.b * p.y + p.b * ry << " m " << p.b << endl;) c[p.x-r+i][max(1,p.y-r)] += (ll) ca - (ll) p.b * p.y + (ll) p.b * ry; m[p.x-r+i][max(1,p.y-r)] += p.b; c[p.x-r+i][max(1,p.y-ry)] -= (ll) ca - (ll) p.b * p.y + (ll) p.b * ry; m[p.x-r+i][max(1,p.y-ry)] -= p.b; c[p.x-r+i][max(1,p.y-ry)] += ca; c[p.x-r+i][min(H+1,p.y+ry+1)] -= ca; //ca - b*(y - (p.y + ry)) = ca + b*p.y + b*ry - b*y DBG(cout << "\t\tVAR c " << ca + p.b * p.y + p.b * ry << " m " << -p.b << endl;) c[p.x-r+i][min(H+1,p.y+ry+1)] += (ll) ca + (ll) p.b * p.y + (ll) p.b * ry; m[p.x-r+i][min(H+1,p.y+ry+1)] += -p.b; c[p.x-r+i][min(H+1,p.y+r+1)] -= (ll) ca + (ll) p.b * p.y + (ll) p.b * ry; m[p.x-r+i][min(H+1,p.y+r+1)] -= -p.b; } FOR(i,0,r-1) if (p.x+r-i <= W) { int ry = r-i; int ca = p.a - p.b * (r - i); DBG(cout << "PROCESS COL " << p.x+r-i << " :: ry " << ry << endl;) //ca - b*((p.y - ry) - y) = ca - b*p.y + b*ry + b*y DBG(cout << "SEG " << max(1,p.y-r) << " " << max(1,p.y-ry) << " " << min(H,p.y+ry+1) << " " << min(H,p.y+r+1) << endl;) c[p.x+r-i][max(1,p.y-r)] += (ll) ca - (ll) p.b * p.y + (ll) p.b * ry; m[p.x+r-i][max(1,p.y-r)] += p.b; c[p.x+r-i][max(1,p.y-ry)] -= (ll) ca - (ll) p.b * p.y + (ll) p.b * ry; m[p.x+r-i][max(1,p.y-ry)] -= p.b; c[p.x+r-i][max(1,p.y-ry)] += ca; c[p.x+r-i][min(H+1,p.y+ry+1)] -= ca; //ca - b*(y - (p.y + ry)) = ca + b*p.y + b*ry - b*y c[p.x+r-i][min(H+1,p.y+ry+1)] += (ll) ca + (ll) p.b * p.y + (ll) p.b * ry; m[p.x+r-i][min(H+1,p.y+ry+1)] += -p.b; c[p.x+r-i][min(H+1,p.y+r+1)] -= (ll) ca + (ll) p.b * p.y + (ll) p.b * ry; m[p.x+r-i][min(H+1,p.y+r+1)] -= -p.b; } } FOR(x,1,W) FOR(y,1,H) { m[x][y] += m[x][y-1]; c[x][y] += c[x][y-1]; v[x][y] = (ll) m[x][y] * y + c[x][y]; v[x][y] += v[x-1][y] + v[x][y-1] - v[x-1][y-1]; } DBG(FOR(x,1,W) { FOR(y,1,H) { cout << m[x][y] << ' '; } cout << endl; } cout << endl;) DBG(FOR(x,1,W) { FOR(y,1,H) { cout << c[x][y] << ' '; } cout << endl; } cout << endl;) DBG(FOR(x,1,W) { FOR(y,1,H) { cout << v[x][y] << ' '; } cout << endl; } cout << endl;) cin >> Q; FOR(q,0,Q-1) { int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2; if (flag) swap(x1,y1), swap(x2,y2); ll s = v[x2][y2] - v[x1-1][y2] - v[x2][y1-1] + v[x1-1][y1-1]; ll r = (ll)(x2-x1+1)*(y2-y1+1); cout << (ll)round((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...