# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
813926 | 2023-08-08T04:38:02 Z | 이동현(#10122) | Posters on the wall (CPSPC17_posters) | C++17 | 878 ms | 964756 KB |
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define int long long using namespace std; struct Node{ int l, r, A, B, Alazy, Blazy; Node(){ l = 0, r = 0, A = 0, B = 0, Alazy = 0, Blazy = 0; } }; const int SZ = (int)1e7, INF = (int)1e9 + 10; Node tr[SZ]; int tn; void push(int x, int s, int e, int ps, int pe, int pa, int pb){ // cout << x << ' ' << s << ' ' << e << ' ' << ps << ' ' << pe << ' ' << pa << ' ' << pb << endl; if(ps <= s && pe >= e){ tr[x].A += pa * (e - s + 1), tr[x].Alazy += pa; tr[x].B += pb * (e - s + 1), tr[x].Blazy += pb; return; } int m = s + e >> 1; if(tr[x].Alazy || tr[x].Blazy || ps <= m){ tr[++tn] = tr[tr[x].l]; tr[x].l = tn; } if(tr[x].Alazy || tr[x].Blazy || pe > m){ tr[++tn] = tr[tr[x].r]; tr[x].r = tn; } tr[tr[x].l].A += tr[x].Alazy * (m - s + 1), tr[tr[x].l].Alazy += tr[x].Alazy; tr[tr[x].l].B += tr[x].Blazy * (m - s + 1), tr[tr[x].l].Blazy += tr[x].Blazy; tr[tr[x].r].A += tr[x].Alazy * (e - m), tr[tr[x].r].Alazy += tr[x].Alazy; tr[tr[x].r].B += tr[x].Blazy * (e - m), tr[tr[x].r].Blazy += tr[x].Blazy; tr[x].Alazy = tr[x].Blazy = 0; if(ps <= m){ push(tr[x].l, s, m, ps, pe, pa, pb); } if(pe > m){ push(tr[x].r, m + 1, e, ps, pe, pa, pb); } tr[x].A = tr[tr[x].l].A + tr[tr[x].r].A; tr[x].B = tr[tr[x].l].B + tr[tr[x].r].B; } pair<int, int> get(int x, int s, int e, int fs, int fe){ if(fe < s || fs > e) return {0, 0}; if(fs <= s && fe >= e){ return {tr[x].A, tr[x].B}; } int m = s + e >> 1; if(tr[x].Alazy || tr[x].Blazy){ tr[++tn] = tr[tr[x].l]; tr[x].l = tn; tr[++tn] = tr[tr[x].r]; tr[x].r = tn; tr[tr[x].l].A += tr[x].Alazy * (m - s + 1), tr[tr[x].l].Alazy += tr[x].Alazy; tr[tr[x].l].B += tr[x].Blazy * (m - s + 1), tr[tr[x].l].Blazy += tr[x].Blazy; tr[tr[x].r].A += tr[x].Alazy * (e - m), tr[tr[x].r].Alazy += tr[x].Alazy; tr[tr[x].r].B += tr[x].Blazy * (e - m), tr[tr[x].r].Blazy += tr[x].Blazy; tr[x].Alazy = tr[x].Blazy = 0; } auto lv = get(tr[x].l, s, m, fs, fe); auto rv = get(tr[x].r, m + 1, e, fs, fe); return {lv.first + rv.first, lv.second + rv.second}; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); int h, w, n, m, mod; cin >> h >> w >> n >> m >> mod; vector<array<int, 5>> que; vector<int> srt; for(int i = 0; i < n; ++i){ int x1, y1, x2, y2; cin >> y1 >> x1 >> y2 >> x2; if(x1 > x2) swap(x1, x2); if(y1 > y2) swap(y1, y2); que.push_back({x1, y1, y2 - 1, 1, -x1}); que.push_back({x2, y1, y2 - 1, -1, x2}); srt.push_back(x1); srt.push_back(x2); } sort(que.begin(), que.end()); sort(srt.begin(), srt.end()); srt.erase(unique(srt.begin(), srt.end()), srt.end()); vector<int> rt((int)srt.size()); int lst = 0; for(auto&[x, y1, y2, A, B]:que){ int nrt = ++tn; tr[nrt] = tr[lst]; push(nrt, 0, h - 1, y1, y2, A, B); // cout << tr[nrt].A << ' ' << tr[nrt].B << endl; int pos = lower_bound(srt.begin(), srt.end(), x) - srt.begin(); rt[pos] = nrt; lst = nrt; } int preans = 0; for(int rep = 0; rep < m; ++rep){ int x1, y1, x2, y2, v; cin >> y1 >> x1 >> y2 >> x2 >> v; x1 = (x1 + preans * v) % mod; x2 = (x2 + preans * v) % mod; y1 = (y1 + preans * v) % mod; y2 = (y2 + preans * v) % mod; if(x1 > x2) swap(x1, x2); if(y1 > y2) swap(y1, y2); auto sol = [&](int x, int y1, int y2)->int{ int pos = lower_bound(srt.begin(), srt.end(), x + 1) - srt.begin() - 1; if(pos < 0){ return 0; } auto rv = get(rt[pos], 0, h - 1, y1, y2 - 1); // cout << pos << ' ' << rv.first << ' ' << rv.second << endl; return rv.first * x + rv.second; }; preans = sol(x2, y1, y2) - sol(x1, y1, y2); // cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl; cout << preans << '\n'; } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 469980 KB | Output is correct |
2 | Correct | 181 ms | 470052 KB | Output is correct |
3 | Correct | 154 ms | 469924 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 469980 KB | Output is correct |
2 | Correct | 181 ms | 470052 KB | Output is correct |
3 | Correct | 154 ms | 469924 KB | Output is correct |
4 | Correct | 168 ms | 470780 KB | Output is correct |
5 | Correct | 164 ms | 470728 KB | Output is correct |
6 | Correct | 165 ms | 470780 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 469980 KB | Output is correct |
2 | Correct | 181 ms | 470052 KB | Output is correct |
3 | Correct | 154 ms | 469924 KB | Output is correct |
4 | Correct | 168 ms | 470780 KB | Output is correct |
5 | Correct | 164 ms | 470728 KB | Output is correct |
6 | Correct | 165 ms | 470780 KB | Output is correct |
7 | Correct | 282 ms | 476068 KB | Output is correct |
8 | Correct | 589 ms | 476188 KB | Output is correct |
9 | Correct | 383 ms | 476072 KB | Output is correct |
10 | Correct | 491 ms | 476088 KB | Output is correct |
11 | Correct | 437 ms | 476128 KB | Output is correct |
12 | Correct | 435 ms | 476144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 469980 KB | Output is correct |
2 | Correct | 181 ms | 470052 KB | Output is correct |
3 | Correct | 154 ms | 469924 KB | Output is correct |
4 | Correct | 168 ms | 470780 KB | Output is correct |
5 | Correct | 164 ms | 470728 KB | Output is correct |
6 | Correct | 165 ms | 470780 KB | Output is correct |
7 | Correct | 387 ms | 476228 KB | Output is correct |
8 | Runtime error | 878 ms | 964756 KB | Execution killed with signal 11 |
9 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 157 ms | 469980 KB | Output is correct |
2 | Correct | 181 ms | 470052 KB | Output is correct |
3 | Correct | 154 ms | 469924 KB | Output is correct |
4 | Correct | 168 ms | 470780 KB | Output is correct |
5 | Correct | 164 ms | 470728 KB | Output is correct |
6 | Correct | 165 ms | 470780 KB | Output is correct |
7 | Correct | 282 ms | 476068 KB | Output is correct |
8 | Correct | 589 ms | 476188 KB | Output is correct |
9 | Correct | 383 ms | 476072 KB | Output is correct |
10 | Correct | 491 ms | 476088 KB | Output is correct |
11 | Correct | 437 ms | 476128 KB | Output is correct |
12 | Correct | 435 ms | 476144 KB | Output is correct |
13 | Correct | 387 ms | 476228 KB | Output is correct |
14 | Runtime error | 878 ms | 964756 KB | Execution killed with signal 11 |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 252 ms | 477352 KB | Output is correct |
2 | Correct | 524 ms | 478624 KB | Output is correct |
3 | Correct | 368 ms | 478588 KB | Output is correct |
4 | Correct | 504 ms | 478692 KB | Output is correct |
5 | Correct | 403 ms | 478672 KB | Output is correct |
6 | Correct | 451 ms | 478636 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 252 ms | 477352 KB | Output is correct |
2 | Correct | 524 ms | 478624 KB | Output is correct |
3 | Correct | 368 ms | 478588 KB | Output is correct |
4 | Correct | 504 ms | 478692 KB | Output is correct |
5 | Correct | 403 ms | 478672 KB | Output is correct |
6 | Correct | 451 ms | 478636 KB | Output is correct |
7 | Incorrect | 501 ms | 479964 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |