#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
#define int long long
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[25252525];
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);
}
signed 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 * v) % m;
x2 = (x2 + prv * v) % m;
y1 = (y1 + prv * v) % m;
y2 = (y2 + prv * 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 'long long int upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = s + e >> 1;
| ~~^~~
Main.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
872 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
872 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
872 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
872 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
872 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
580 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
580 ms |
1048580 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
