#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#define pii pair<int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
using namespace std;
int cnt = 1;
struct Node
{
long long a, b, c, d;
int l, r;
Node(void) : a(0), b(0), c(0), d(0), l(-1), r(-1) {}
}seg[20202020];
int upd(int ind, int s, int e, int pos, long long a, long long b, long long c, long long d)
{
int ret = cnt++;
if(ind != -1) seg[ret] = seg[ind];
if(s + 1 == e)
{
seg[ret].a += a;
seg[ret].b += b;
seg[ret].c += c;
seg[ret].d += d;
return ret;
}
int mid = s + e >> 1;
if(pos < mid) seg[ret].l = upd(seg[ret].l, s, mid, pos, a, b, c, d);
else seg[ret].r = upd(seg[ret].r, mid, e, pos, a, b, c, d);
seg[ret].a = 0;
if(seg[ret].l != -1) seg[ret].a += seg[seg[ret].l].a;
if(seg[ret].r != -1) seg[ret].a += seg[seg[ret].r].a;
seg[ret].b = 0;
if(seg[ret].l != -1) seg[ret].b += seg[seg[ret].l].b;
if(seg[ret].r != -1) seg[ret].b += seg[seg[ret].r].b;
seg[ret].c = 0;
if(seg[ret].l != -1) seg[ret].c += seg[seg[ret].l].c;
if(seg[ret].r != -1) seg[ret].c += seg[seg[ret].r].c;
seg[ret].d = 0;
if(seg[ret].l != -1) seg[ret].d += seg[seg[ret].l].d;
if(seg[ret].r != -1) seg[ret].d += seg[seg[ret].r].d;
return ret;
}
long long qry(int ind, int s, int e, int l, int r, int x, int y)
{
if(e <= l || r <= s || ind == -1) return 0;
if(l <= s && e <= r)
{
// cout << seg[ind].a << ' ' << seg[ind].b << ' ' << seg[ind].c << ' ' << seg[ind].d << endl;
return seg[ind].a * x * y - seg[ind].b * x - seg[ind].c * y + seg[ind].d;
}
int mid = s + e >> 1;
return qry(seg[ind].l, s, mid, l, r, x, y) + qry(seg[ind].r, mid, e, l, r, x, y);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("in.txt", "r", stdin);
int r, c, n, T, m; cin >> r >> c >> n >> T >> m; r += 2; c += 2;
tiiii rec[n];
vector<int> pr;
for(int i = 0; i < n; ++i)
{
int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
rec[i] = {x1, y1, x2, y2};
pr.push_back(y1);
pr.push_back(y2);
}
sort(pr.begin(), pr.end());
pr.resize(unique(pr.begin(), pr.end()) - pr.begin());
c = pr.size();
vector<pii> ls[c];
for(auto &[x1, y1, x2, y2] : rec)
{
y1 = lower_bound(pr.begin(), pr.end(), y1) - pr.begin();
y2 = lower_bound(pr.begin(), pr.end(), y2) - pr.begin();
ls[y1].push_back({x1, 1});
ls[y1].push_back({x2, -1});
ls[y2].push_back({x1, -1});
ls[y2].push_back({x2, 1});
}
int root[c + 1]; root[0] = 0;
for(int y = 0; y < c; ++y)
{
root[y + 1] = root[y];
for(auto [x, t] : ls[y])
root[y + 1] = upd(root[y + 1], 0, r, x, t, pr[y] * t, x * t, 1ll * x * pr[y] * t);
}
long long prv = 0;
while(T--)
{
int x1, x2, y1, y2, v; cin >> x1 >> y1 >> x2 >> y2 >> v;
x1 = (x1 + prv % m * v) % m;
x2 = (x2 + prv % m * v) % m;
y1 = (y1 + prv % m * v) % m;
y2 = (y2 + prv % m * v) % m;
if(x1 > x2) swap(x1, x2);
if(y1 > y2) swap(y1, y2);
int yi1 = lower_bound(pr.begin(), pr.end(), y1) - pr.begin();
int yi2 = lower_bound(pr.begin(), pr.end(), y2) - pr.begin();
// cout << qry(root[y2], 0, r, 0, x2, x2, y2) << endl;
prv = qry(root[yi2], 0, r, 0, x2, x2, y2) - qry(root[yi2], 0, r, 0, x1, x1, y2)
-qry(root[yi1], 0, r, 0, x2, x2, y1) + qry(root[yi1], 0, r, 0, x1, x1, y1);
cout << prv << '\n';
}
}
Compilation message
Main.cpp: In function 'int upd(int, int, int, int, long long int, long long int, long long int, long long int)':
Main.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'long long int qry(int, int, int, int, int, int, int)':
Main.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = s + e >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
790932 KB |
Output is correct |
2 |
Correct |
382 ms |
790976 KB |
Output is correct |
3 |
Correct |
379 ms |
790928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
790932 KB |
Output is correct |
2 |
Correct |
382 ms |
790976 KB |
Output is correct |
3 |
Correct |
379 ms |
790928 KB |
Output is correct |
4 |
Correct |
419 ms |
791468 KB |
Output is correct |
5 |
Correct |
405 ms |
791436 KB |
Output is correct |
6 |
Correct |
457 ms |
791480 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
790932 KB |
Output is correct |
2 |
Correct |
382 ms |
790976 KB |
Output is correct |
3 |
Correct |
379 ms |
790928 KB |
Output is correct |
4 |
Correct |
419 ms |
791468 KB |
Output is correct |
5 |
Correct |
405 ms |
791436 KB |
Output is correct |
6 |
Correct |
457 ms |
791480 KB |
Output is correct |
7 |
Correct |
588 ms |
796168 KB |
Output is correct |
8 |
Correct |
979 ms |
797792 KB |
Output is correct |
9 |
Correct |
671 ms |
796912 KB |
Output is correct |
10 |
Correct |
873 ms |
797604 KB |
Output is correct |
11 |
Correct |
748 ms |
796240 KB |
Output is correct |
12 |
Correct |
685 ms |
797756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
790932 KB |
Output is correct |
2 |
Correct |
382 ms |
790976 KB |
Output is correct |
3 |
Correct |
379 ms |
790928 KB |
Output is correct |
4 |
Correct |
419 ms |
791468 KB |
Output is correct |
5 |
Correct |
405 ms |
791436 KB |
Output is correct |
6 |
Correct |
457 ms |
791480 KB |
Output is correct |
7 |
Correct |
684 ms |
795932 KB |
Output is correct |
8 |
Correct |
1148 ms |
797656 KB |
Output is correct |
9 |
Correct |
888 ms |
796996 KB |
Output is correct |
10 |
Correct |
936 ms |
797664 KB |
Output is correct |
11 |
Correct |
861 ms |
796304 KB |
Output is correct |
12 |
Correct |
761 ms |
797672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
382 ms |
790932 KB |
Output is correct |
2 |
Correct |
382 ms |
790976 KB |
Output is correct |
3 |
Correct |
379 ms |
790928 KB |
Output is correct |
4 |
Correct |
419 ms |
791468 KB |
Output is correct |
5 |
Correct |
405 ms |
791436 KB |
Output is correct |
6 |
Correct |
457 ms |
791480 KB |
Output is correct |
7 |
Correct |
588 ms |
796168 KB |
Output is correct |
8 |
Correct |
979 ms |
797792 KB |
Output is correct |
9 |
Correct |
671 ms |
796912 KB |
Output is correct |
10 |
Correct |
873 ms |
797604 KB |
Output is correct |
11 |
Correct |
748 ms |
796240 KB |
Output is correct |
12 |
Correct |
685 ms |
797756 KB |
Output is correct |
13 |
Correct |
684 ms |
795932 KB |
Output is correct |
14 |
Correct |
1148 ms |
797656 KB |
Output is correct |
15 |
Correct |
888 ms |
796996 KB |
Output is correct |
16 |
Correct |
936 ms |
797664 KB |
Output is correct |
17 |
Correct |
861 ms |
796304 KB |
Output is correct |
18 |
Correct |
761 ms |
797672 KB |
Output is correct |
19 |
Correct |
734 ms |
798196 KB |
Output is correct |
20 |
Correct |
1046 ms |
798852 KB |
Output is correct |
21 |
Correct |
731 ms |
797124 KB |
Output is correct |
22 |
Correct |
958 ms |
798540 KB |
Output is correct |
23 |
Correct |
857 ms |
797008 KB |
Output is correct |
24 |
Correct |
745 ms |
798760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
580 ms |
795332 KB |
Output is correct |
2 |
Correct |
902 ms |
796924 KB |
Output is correct |
3 |
Correct |
690 ms |
796744 KB |
Output is correct |
4 |
Correct |
822 ms |
796824 KB |
Output is correct |
5 |
Correct |
712 ms |
795928 KB |
Output is correct |
6 |
Correct |
740 ms |
796912 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
580 ms |
795332 KB |
Output is correct |
2 |
Correct |
902 ms |
796924 KB |
Output is correct |
3 |
Correct |
690 ms |
796744 KB |
Output is correct |
4 |
Correct |
822 ms |
796824 KB |
Output is correct |
5 |
Correct |
712 ms |
795928 KB |
Output is correct |
6 |
Correct |
740 ms |
796912 KB |
Output is correct |
7 |
Correct |
725 ms |
798204 KB |
Output is correct |
8 |
Correct |
1008 ms |
798808 KB |
Output is correct |
9 |
Correct |
783 ms |
797040 KB |
Output is correct |
10 |
Correct |
937 ms |
798640 KB |
Output is correct |
11 |
Correct |
803 ms |
797156 KB |
Output is correct |
12 |
Correct |
751 ms |
798800 KB |
Output is correct |