#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[25000005];
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);
}
}
ll 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 << 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;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
366 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
326 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
326 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
