| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 142787 |
2019-08-11T03:34:32 Z |
lyc |
Nuclearia (CEOI15_nuclearia) |
C++14 |
|
759 ms |
110872 KB |
//#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 = 2500100;
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) + x]; }
} nuclearia, posDiag, negDiag, row, col;
inline void addSquare(int sx, int sy, int ex, int ey, ll c) {
sx = max(0, sx);
sy = max(0, sy);
nuclearia(sx , sy ) += c;
if (ex+1 <= W-1) nuclearia(ex+1, sy ) -= c;
if (ey+1 <= H-1) nuclearia(sx , ey+1) -= c;
if (ex+1 <= W-1 and ey+1 <= H-1) nuclearia(ex+1, ey+1) += c;
}
inline void addCol(int x, int sy, int ey, ll m) {
assert(x >= 0 and x < W and sy >= 0 and ey < H);
col(x,sy) += m;
if (ey+1 <= H-1) col(x,ey+1) -= m;
}
inline void addRow(int y, int sx, int ex, ll m) {
assert(y >= 0 and y < H and sx >= 0 and ex < W);
row(sx,y) += m;
if (ex+1 <= W-1) 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 < 0 and sy < 0) {
int out = min(0-sx, 0-sy);
nuclearia(0,0) += (ll) out * m;
sx += out, sy += out;
}
if (sx < 0) {
int out = 0-sx;
addCol(0,sy,sy+out-1,m);
sx += out, sy += out;
}
if (sy < 0) {
int out = 0-sy;
addRow(0,sx,sx+out-1,m);
sx += out, sy += out;
}
negDiag(sx, sy) += m;
if (ex+1 <= W-1 and ey+1 <= H-1) 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 (sy >= H) {
int out = sy-(H-1);
sx += out, sy -= out;
}
if (sx < 0) {
int out = 0-sx;
addCol(0,sy-out+1,sy,m);
sx += out, sy -= out;
}
if (ex >= W) {
int out = ex-(W-1);
ex -= out, ey += out;
}
if (ey < 0) {
int out = 0-ey;
addRow(0,ex-out+1,ex,m);
ex -= out, ey += out;
}
posDiag(sx, sy) += m;
if (ex+1 <= W-1 and ey-1 >= 0) posDiag(ex+1, max(0,ey-1)) -= m;
}
inline void summariseDiags() {
FOR(x,1,W-1) FOR(y,0,H-1) {
if (y-1 >= 0) negDiag(x,y) += negDiag(x-1,y-1);
if (y+1 <= H-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,0,W-1) FOR(y,0,H-1) {
nuclearia(x,y) += negDiag(x,y) + posDiag(x,y);
}
}
inline void summariseLines() {
FOR(x,0,W-1) FOR(y,0,H-1) {
if (x-1 >= 0) row(x,y) += row(x-1,y);
if (y-1 >= 0) 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,0,W-1) FOR(y,0,H-1) {
nuclearia(x,y) += row(x,y) + col(x,y);
}
}
inline void summarise() {
FOR(x,0,W-1) FOR(y,0,H-1) {
//col(x,y) += col(x,y-1);
//nuclearia(x, y) += nuclearia(x-1, y) + nuclearia(x, y-1) - nuclearia(x-1, y-1);
if (x-1 >= 0) nuclearia(x,y) += nuclearia(x-1,y);
if (y-1 >= 0) nuclearia(x,y) += nuclearia(x,y-1);
if (x-1 >= 0 and y-1 >= 0) nuclearia(x,y) -= nuclearia(x-1,y-1);
}
DBG(cout << "NUCLEARIA " << endl; FOR(y,0,H-1) { FOR(x,0,W-1) { 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-1,y-1,a,b}; }
//int idx = 0;
for (Plant p : plant) {
//++idx;
//if (idx != 1) continue;
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,0,H-1) { FOR(x,0,W-1) { cout << nuclearia(x,y) << ' '; } cout << endl; })
summarise(); // calc nuclearia
summarise(); // calc nuclearia_pre
DBG(ll g[W][H]; memset(g, 0, sizeof g);
FOR(x,0,W-1) FOR(y,0,H-1) {
for (Plant p : plant) {
g[x][y] += max(0, p.a - p.b * max(abs(x-p.x),abs(y-p.y)));
}
}
FOR(y,0,H-1) { FOR(x,0,W-1) { cout << g[x][y] << ' '; } cout << endl; }
FOR(x,0,W-1) FOR(y,0,H-1) {
if (x-1 >= 0) g[x][y] += g[x-1][y];
if (y-1 >= 0) g[x][y] += g[x][y-1];
if (x-1 >= 0 and y-1 >= 0) g[x][y] -= g[x-1][y-1];
}
cout << endl;
FOR(y,0,H-1) { FOR(x,0,W-1) { cout << g[x][y] << ' '; } cout << endl; })
cin >> Q; FOR(q,0,Q-1) {
int x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
--x1,--y1,--x2,--y2;
ll s = nuclearia(x2,y2);
if (x1-1 >= 0) s -= nuclearia(x1-1,y2);
if (y1-1 >= 0) s -= nuclearia(x2,y1-1);
if (x1-1 >= 0 and y1-1 >= 0) s += nuclearia(x1-1,y1-1);
DBG(ll s2 = g[x2][y2];
if (x1-1 >= 0) s2 -= g[x1-1][y2];
if (y1-1 >= 0) s2 -= g[x2][y1-1];
if (x1-1 >= 0 and y1-1 >= 0) s2 += g[x1-1][y1-1];
cout << s << " " << s2 << endl;)
ll r = (ll)(x2-x1+1)*(y2-y1+1);
cout << (ll)round((long double)s/r) << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
39928 KB |
Output is correct |
| 2 |
Correct |
88 ms |
4920 KB |
Output is correct |
| 3 |
Correct |
78 ms |
4024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
39928 KB |
Output is correct |
| 2 |
Correct |
87 ms |
4732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
98156 KB |
Output is correct |
| 2 |
Correct |
85 ms |
4368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
98228 KB |
Output is correct |
| 2 |
Correct |
86 ms |
4724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
45760 KB |
Output is correct |
| 2 |
Correct |
89 ms |
5368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
22812 KB |
Output is correct |
| 2 |
Correct |
86 ms |
4728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
614 ms |
104012 KB |
Output is correct |
| 2 |
Correct |
90 ms |
4984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
167 ms |
34460 KB |
Output is correct |
| 2 |
Correct |
88 ms |
4600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
345 ms |
91612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
342 ms |
91656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
450 ms |
110872 KB |
Output is correct |
| 2 |
Correct |
759 ms |
110868 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
681 ms |
110796 KB |
Output is correct |
| 2 |
Correct |
710 ms |
110712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
555 ms |
110700 KB |
Output is correct |
| 2 |
Correct |
390 ms |
110620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
417 ms |
110676 KB |
Output is correct |
| 2 |
Correct |
336 ms |
91512 KB |
Output is correct |
