#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)21500000;
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);
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);
return rv.first * x + rv.second;
};
preans = sol(x2, y1, y2) - sol(x1, y1, y2);
cout << preans << '\n';
}
assert(tn < SZ);
return 0;
}
Compilation message
Main.cpp: In function 'void push(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int m = s + e >> 1;
| ~~^~~
Main.cpp: In function 'std::pair<long long int, long long int> get(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int m = s + e >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
1010136 KB |
Output is correct |
2 |
Correct |
310 ms |
1010140 KB |
Output is correct |
3 |
Correct |
311 ms |
1010056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
1010136 KB |
Output is correct |
2 |
Correct |
310 ms |
1010140 KB |
Output is correct |
3 |
Correct |
311 ms |
1010056 KB |
Output is correct |
4 |
Correct |
320 ms |
1010784 KB |
Output is correct |
5 |
Correct |
320 ms |
1010796 KB |
Output is correct |
6 |
Correct |
324 ms |
1010824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
1010136 KB |
Output is correct |
2 |
Correct |
310 ms |
1010140 KB |
Output is correct |
3 |
Correct |
311 ms |
1010056 KB |
Output is correct |
4 |
Correct |
320 ms |
1010784 KB |
Output is correct |
5 |
Correct |
320 ms |
1010796 KB |
Output is correct |
6 |
Correct |
324 ms |
1010824 KB |
Output is correct |
7 |
Correct |
417 ms |
1016236 KB |
Output is correct |
8 |
Correct |
713 ms |
1016200 KB |
Output is correct |
9 |
Correct |
516 ms |
1016204 KB |
Output is correct |
10 |
Correct |
694 ms |
1016380 KB |
Output is correct |
11 |
Correct |
576 ms |
1016244 KB |
Output is correct |
12 |
Correct |
593 ms |
1016364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
1010136 KB |
Output is correct |
2 |
Correct |
310 ms |
1010140 KB |
Output is correct |
3 |
Correct |
311 ms |
1010056 KB |
Output is correct |
4 |
Correct |
320 ms |
1010784 KB |
Output is correct |
5 |
Correct |
320 ms |
1010796 KB |
Output is correct |
6 |
Correct |
324 ms |
1010824 KB |
Output is correct |
7 |
Correct |
558 ms |
1016348 KB |
Output is correct |
8 |
Correct |
897 ms |
1016352 KB |
Output is correct |
9 |
Correct |
678 ms |
1016232 KB |
Output is correct |
10 |
Correct |
860 ms |
1016436 KB |
Output is correct |
11 |
Correct |
739 ms |
1016376 KB |
Output is correct |
12 |
Correct |
703 ms |
1016400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
330 ms |
1010136 KB |
Output is correct |
2 |
Correct |
310 ms |
1010140 KB |
Output is correct |
3 |
Correct |
311 ms |
1010056 KB |
Output is correct |
4 |
Correct |
320 ms |
1010784 KB |
Output is correct |
5 |
Correct |
320 ms |
1010796 KB |
Output is correct |
6 |
Correct |
324 ms |
1010824 KB |
Output is correct |
7 |
Correct |
417 ms |
1016236 KB |
Output is correct |
8 |
Correct |
713 ms |
1016200 KB |
Output is correct |
9 |
Correct |
516 ms |
1016204 KB |
Output is correct |
10 |
Correct |
694 ms |
1016380 KB |
Output is correct |
11 |
Correct |
576 ms |
1016244 KB |
Output is correct |
12 |
Correct |
593 ms |
1016364 KB |
Output is correct |
13 |
Correct |
558 ms |
1016348 KB |
Output is correct |
14 |
Correct |
897 ms |
1016352 KB |
Output is correct |
15 |
Correct |
678 ms |
1016232 KB |
Output is correct |
16 |
Correct |
860 ms |
1016436 KB |
Output is correct |
17 |
Correct |
739 ms |
1016376 KB |
Output is correct |
18 |
Correct |
703 ms |
1016400 KB |
Output is correct |
19 |
Correct |
582 ms |
1016596 KB |
Output is correct |
20 |
Correct |
891 ms |
1016596 KB |
Output is correct |
21 |
Correct |
705 ms |
1016336 KB |
Output is correct |
22 |
Correct |
860 ms |
1016532 KB |
Output is correct |
23 |
Correct |
821 ms |
1016584 KB |
Output is correct |
24 |
Correct |
780 ms |
1016504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
442 ms |
1016220 KB |
Output is correct |
2 |
Correct |
715 ms |
1016152 KB |
Output is correct |
3 |
Correct |
586 ms |
1016200 KB |
Output is correct |
4 |
Correct |
744 ms |
1016156 KB |
Output is correct |
5 |
Correct |
613 ms |
1016228 KB |
Output is correct |
6 |
Correct |
673 ms |
1016232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
442 ms |
1016220 KB |
Output is correct |
2 |
Correct |
715 ms |
1016152 KB |
Output is correct |
3 |
Correct |
586 ms |
1016200 KB |
Output is correct |
4 |
Correct |
744 ms |
1016156 KB |
Output is correct |
5 |
Correct |
613 ms |
1016228 KB |
Output is correct |
6 |
Correct |
673 ms |
1016232 KB |
Output is correct |
7 |
Incorrect |
676 ms |
1016176 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |