#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)23000000;
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
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 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
390 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
324 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
324 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
