# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
125553 | 2019-07-05T23:11:42 Z | eriksuenderhauf | Nuclearia (CEOI15_nuclearia) | C++11 | 1000 ms | 161132 KB |
//#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/rope> #define mem(a,v) memset((a), (v), sizeof (a)) #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pil pair<int, long long> #define pll pair<long long, long long> #define vii vector<pii> #define vil vector<pil> #define vll vector<pll> #define vi vector<int> #define vl vector<long long> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e6 + 5; const double eps = 1e-9; vector<vl> off, sl, sm; int main() { int w, h, n; scanf("%d %d %d", &w, &h, &n); off.resize(h+1); sl.resize(h+1), sm.resize(h+1); for (int i = 0; i <= h; i++) off[i].resize(w+3), sl[i].resize(w+3), sm[i].resize(w+3); for (int i = 0; i < n; i++) { ll x, y, a, b; scanf("%lld %lld %lld %lld", &x, &y, &a, &b); ll l = max(1ll, x - a / b), r = min((ll)w, x + a / b); for (ll j = max(1ll, y - a / b); j <= min((ll)h, y + a / b); j++) { off[j][l] += a; off[j][r+1] -= a; sl[j][l] -= b * (x-l); sl[j][l+1] += b * (x-l+1); sl[j][x+1-abs(y-j)] -= b; sl[j][x+1+abs(y-j)] -= b; sl[j][r+1] += b*(r-x+1); sl[j][r+2] -= b*(r-x); } } for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { off[i][j] += off[i][j-1]; sl[i][j] += sl[i][j-1]; } for (int j = 1; j <= w; j++) sl[i][j] += sl[i][j-1]; for (int j = 1; j <= w; j++) sm[i][j] = sm[i-1][j] + sm[i][j-1] - sm[i-1][j-1] + sl[i][j] + off[i][j]; } int q; ni(q); while (q--) { ll x1, y1, x2, y2; scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2); ll ans = sm[y2][x2] - sm[y1-1][x2] - sm[y2][x1-1] + sm[y1-1][x1-1]; x1 = (x2-x1+1) * (y2-y1+1); if ((ans % x1) * 2 >= x1) prl(ans / x1 + 1); else prl(ans / x1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 117752 KB | Output is correct |
2 | Correct | 99 ms | 2680 KB | Output is correct |
3 | Correct | 88 ms | 2296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 120 ms | 117800 KB | Output is correct |
2 | Correct | 103 ms | 2676 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 159 ms | 119672 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 | 194 ms | 161132 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 | Correct | 288 ms | 119924 KB | Output is correct |
2 | Correct | 106 ms | 2936 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 201 ms | 49716 KB | Output is correct |
2 | Correct | 100 ms | 2736 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 353 ms | 123384 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 | Correct | 188 ms | 38012 KB | Output is correct |
2 | Runtime error | 99 ms | 4600 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 392 ms | 120184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 398 ms | 120236 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1084 ms | 59128 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1068 ms | 59256 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 144 ms | 126840 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 | Execution timed out | 1087 ms | 59228 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |