| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 142692 |
2019-08-10T13:55:51 Z |
lyc |
Nuclearia (CEOI15_nuclearia) |
C++14 |
|
726 ms |
111540 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 = 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 time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
98224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
412 ms |
103156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
9 ms |
632 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
188 ms |
45524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
618 ms |
104356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
191 ms |
45476 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
10564 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
10744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
449 ms |
110820 KB |
Output is correct |
| 2 |
Correct |
726 ms |
111004 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
640 ms |
110968 KB |
Output is correct |
| 2 |
Correct |
724 ms |
111096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
111540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
426 ms |
110768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
