#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
using ll = long long;
struct Eq
{
ll xy, x, y, c;
Eq()
{
xy = x = y = c = 0;
}
Eq(ll _xy, ll _x, ll _y, ll _c)
{
xy = _xy, x = _x, y = _y, c = _c;
}
Eq operator+(Eq e) {
Eq eq;
eq.xy = xy + e.xy, eq.x = x + e.x, eq.y = y + e.y, eq.c = c + e.c;
return eq;
}
Eq& operator+=(const Eq& e)
{
xy += e.xy; x += e.x; y += e.y; c += e.c;
return *this;
}
ll calc(ll a, ll b)
{
return xy * a * b + x * a + y * b + c;
}
};
struct Node
{
int l, r;
Eq val;
Node()
{
l = r = -1;
}
};
const int inf = 2e9;
struct PDST
{
Node tree[20000005];
int pv;
int root[400005];
int addNode()
{
Node node;
tree[pv++] = node;
return pv - 1;
}
PDST()
{
root[0] = addNode();
}
void push(int i)
{
root[i] = addNode();
tree[root[i]] = tree[root[i-1]];
}
void update(int node, int s, int e, int id, Eq eq)
{
tree[node].val += eq;
if (s == e) return;
int m = s + e >> 1;
if (id <= m) {
int prev = tree[node].l;
tree[node].l = addNode();
if (prev != -1) tree[tree[node].l] = tree[prev];
update(tree[node].l, s, m, id, eq);
}
else {
int prev = tree[node].r;
tree[node].r = addNode();
if (prev != -1) tree[tree[node].r] = tree[prev];
update(tree[node].r, m+1, e, id, eq);
}
}
Eq query(int node, int s, int e, int l, int r)
{
if (e < l || r < s) return {};
if (l <= s && e <= r) return tree[node].val;
Eq ret = {};
int m = s + e >> 1;
if (tree[node].l != -1) ret += query(tree[node].l, s, m, l, r);
if (tree[node].r != -1) ret += query(tree[node].r, m+1, e, l, r);
return ret;
}
};
PDST seg;
struct Query
{
int x1, x2;
int sgn, id;
int y;
Query(int _x1, int _x2, int _sgn, int _id, int _y)
{
x1 = _x1, x2 = _x2, sgn = _sgn, id = _id, y = _y;
}
};
struct Update
{
int x;
Eq eq;
int y;
Update(int _x, Eq _eq, int _y)
{
x = _x, eq = _eq, y = _y;
}
};
int N, Q;
vector<Update> upd[400005], upds;
signed main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int R, C, M; cin >> R >> C >> N >> Q >> M;
vector<int> cpx;
for (int i = 0; i < N; i++) {
ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
upds.push_back({x1+1, {1, -y1, -x1, x1*y1}, y1+1});
upds.push_back({x2+1, {-1, y1, x2, -x2*y1}, y1+1});
upds.push_back({x1+1, {-1, y2, x1, -x1*y2}, y2+1});
upds.push_back({x2+1, {1, -y2, -x2, x2*y2}, y2+1});
cpx.push_back(y1+1); cpx.push_back(y2+1);
}
cpx.push_back(0);
sort(cpx.begin(), cpx.end());
for (auto p:upds) {
upd[lower_bound(cpx.begin(), cpx.end(), p.y)-cpx.begin()].push_back(p);
}
for (int i = 1; i < (int)cpx.size(); i++) {
seg.push(i);
for (auto p:upd[i]) {
seg.update(seg.root[i], 1, inf, p.x, p.eq);
}
}
__int128_t ans = 0;
while (Q--) {
ll x1, y1, x2, y2, v; cin >> x1 >> y1 >> x2 >> y2 >> v;
x1 = (x1 + ans * v) % M, x2 = (x2 + ans * v) % M, y1 = (y1 + ans * v) % M, y2 = (y2 + ans * v) % M;
ans = 0;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
int pos = upper_bound(cpx.begin(), cpx.end(), y2) - cpx.begin() - 1;
ans += seg.query(seg.root[pos], 1, inf, 1, x2).calc(x2, y2);
if (x1) ans -= seg.query(seg.root[pos], 1, inf, 1, x1).calc(x1, y2);
int pos2 = upper_bound(cpx.begin(), cpx.end(), y1) - cpx.begin() - 1;
ans -= seg.query(seg.root[pos2], 1, inf, 1, x2).calc(x2, y1);
if (x1) ans += seg.query(seg.root[pos2], 1, inf, 1, x1).calc(x1, y1);
cout << (ll)ans << '\n';
}
return 0;
}
Compilation message
Main.cpp: In member function 'void PDST::update(long long int, long long int, long long int, long long int, Eq)':
Main.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int m = s + e >> 1;
| ~~^~~
Main.cpp: In member function 'Eq PDST::query(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int m = s + e >> 1;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
949228 KB |
Output is correct |
2 |
Correct |
335 ms |
949224 KB |
Output is correct |
3 |
Correct |
345 ms |
949204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
949228 KB |
Output is correct |
2 |
Correct |
335 ms |
949224 KB |
Output is correct |
3 |
Correct |
345 ms |
949204 KB |
Output is correct |
4 |
Correct |
381 ms |
951256 KB |
Output is correct |
5 |
Correct |
371 ms |
951436 KB |
Output is correct |
6 |
Correct |
408 ms |
951180 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
949228 KB |
Output is correct |
2 |
Correct |
335 ms |
949224 KB |
Output is correct |
3 |
Correct |
345 ms |
949204 KB |
Output is correct |
4 |
Correct |
381 ms |
951256 KB |
Output is correct |
5 |
Correct |
371 ms |
951436 KB |
Output is correct |
6 |
Correct |
408 ms |
951180 KB |
Output is correct |
7 |
Correct |
496 ms |
971256 KB |
Output is correct |
8 |
Correct |
831 ms |
971632 KB |
Output is correct |
9 |
Correct |
651 ms |
974108 KB |
Output is correct |
10 |
Correct |
754 ms |
971692 KB |
Output is correct |
11 |
Correct |
639 ms |
971948 KB |
Output is correct |
12 |
Correct |
626 ms |
971672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
949228 KB |
Output is correct |
2 |
Correct |
335 ms |
949224 KB |
Output is correct |
3 |
Correct |
345 ms |
949204 KB |
Output is correct |
4 |
Correct |
381 ms |
951256 KB |
Output is correct |
5 |
Correct |
371 ms |
951436 KB |
Output is correct |
6 |
Correct |
408 ms |
951180 KB |
Output is correct |
7 |
Correct |
502 ms |
971548 KB |
Output is correct |
8 |
Correct |
768 ms |
971780 KB |
Output is correct |
9 |
Correct |
570 ms |
974232 KB |
Output is correct |
10 |
Correct |
690 ms |
972088 KB |
Output is correct |
11 |
Correct |
627 ms |
972180 KB |
Output is correct |
12 |
Correct |
585 ms |
971964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
375 ms |
949228 KB |
Output is correct |
2 |
Correct |
335 ms |
949224 KB |
Output is correct |
3 |
Correct |
345 ms |
949204 KB |
Output is correct |
4 |
Correct |
381 ms |
951256 KB |
Output is correct |
5 |
Correct |
371 ms |
951436 KB |
Output is correct |
6 |
Correct |
408 ms |
951180 KB |
Output is correct |
7 |
Correct |
496 ms |
971256 KB |
Output is correct |
8 |
Correct |
831 ms |
971632 KB |
Output is correct |
9 |
Correct |
651 ms |
974108 KB |
Output is correct |
10 |
Correct |
754 ms |
971692 KB |
Output is correct |
11 |
Correct |
639 ms |
971948 KB |
Output is correct |
12 |
Correct |
626 ms |
971672 KB |
Output is correct |
13 |
Correct |
502 ms |
971548 KB |
Output is correct |
14 |
Correct |
768 ms |
971780 KB |
Output is correct |
15 |
Correct |
570 ms |
974232 KB |
Output is correct |
16 |
Correct |
690 ms |
972088 KB |
Output is correct |
17 |
Correct |
627 ms |
972180 KB |
Output is correct |
18 |
Correct |
585 ms |
971964 KB |
Output is correct |
19 |
Correct |
531 ms |
972172 KB |
Output is correct |
20 |
Correct |
786 ms |
972084 KB |
Output is correct |
21 |
Correct |
593 ms |
974312 KB |
Output is correct |
22 |
Correct |
705 ms |
971980 KB |
Output is correct |
23 |
Correct |
625 ms |
972288 KB |
Output is correct |
24 |
Correct |
577 ms |
972088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
517 ms |
971220 KB |
Output is correct |
2 |
Correct |
784 ms |
971672 KB |
Output is correct |
3 |
Correct |
624 ms |
973984 KB |
Output is correct |
4 |
Correct |
743 ms |
971744 KB |
Output is correct |
5 |
Correct |
643 ms |
971888 KB |
Output is correct |
6 |
Correct |
699 ms |
971692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
517 ms |
971220 KB |
Output is correct |
2 |
Correct |
784 ms |
971672 KB |
Output is correct |
3 |
Correct |
624 ms |
973984 KB |
Output is correct |
4 |
Correct |
743 ms |
971744 KB |
Output is correct |
5 |
Correct |
643 ms |
971888 KB |
Output is correct |
6 |
Correct |
699 ms |
971692 KB |
Output is correct |
7 |
Correct |
571 ms |
971992 KB |
Output is correct |
8 |
Correct |
891 ms |
972964 KB |
Output is correct |
9 |
Correct |
726 ms |
974584 KB |
Output is correct |
10 |
Correct |
832 ms |
972852 KB |
Output is correct |
11 |
Correct |
713 ms |
973160 KB |
Output is correct |
12 |
Correct |
640 ms |
972984 KB |
Output is correct |