#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 * 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 '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;
| ~~^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
410 ms |
790976 KB |
Output is correct |
2 |
Correct |
400 ms |
790912 KB |
Output is correct |
3 |
Correct |
392 ms |
790964 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
410 ms |
790976 KB |
Output is correct |
2 |
Correct |
400 ms |
790912 KB |
Output is correct |
3 |
Correct |
392 ms |
790964 KB |
Output is correct |
4 |
Correct |
408 ms |
791424 KB |
Output is correct |
5 |
Correct |
403 ms |
791416 KB |
Output is correct |
6 |
Correct |
393 ms |
791496 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
410 ms |
790976 KB |
Output is correct |
2 |
Correct |
400 ms |
790912 KB |
Output is correct |
3 |
Correct |
392 ms |
790964 KB |
Output is correct |
4 |
Correct |
408 ms |
791424 KB |
Output is correct |
5 |
Correct |
403 ms |
791416 KB |
Output is correct |
6 |
Correct |
393 ms |
791496 KB |
Output is correct |
7 |
Correct |
596 ms |
796100 KB |
Output is correct |
8 |
Correct |
942 ms |
797936 KB |
Output is correct |
9 |
Correct |
696 ms |
796776 KB |
Output is correct |
10 |
Correct |
888 ms |
797648 KB |
Output is correct |
11 |
Correct |
888 ms |
796236 KB |
Output is correct |
12 |
Correct |
805 ms |
798028 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
410 ms |
790976 KB |
Output is correct |
2 |
Correct |
400 ms |
790912 KB |
Output is correct |
3 |
Correct |
392 ms |
790964 KB |
Output is correct |
4 |
Correct |
408 ms |
791424 KB |
Output is correct |
5 |
Correct |
403 ms |
791416 KB |
Output is correct |
6 |
Correct |
393 ms |
791496 KB |
Output is correct |
7 |
Correct |
705 ms |
796100 KB |
Output is correct |
8 |
Correct |
993 ms |
797904 KB |
Output is correct |
9 |
Correct |
751 ms |
797056 KB |
Output is correct |
10 |
Correct |
906 ms |
797548 KB |
Output is correct |
11 |
Correct |
850 ms |
796316 KB |
Output is correct |
12 |
Correct |
750 ms |
797764 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
410 ms |
790976 KB |
Output is correct |
2 |
Correct |
400 ms |
790912 KB |
Output is correct |
3 |
Correct |
392 ms |
790964 KB |
Output is correct |
4 |
Correct |
408 ms |
791424 KB |
Output is correct |
5 |
Correct |
403 ms |
791416 KB |
Output is correct |
6 |
Correct |
393 ms |
791496 KB |
Output is correct |
7 |
Correct |
596 ms |
796100 KB |
Output is correct |
8 |
Correct |
942 ms |
797936 KB |
Output is correct |
9 |
Correct |
696 ms |
796776 KB |
Output is correct |
10 |
Correct |
888 ms |
797648 KB |
Output is correct |
11 |
Correct |
888 ms |
796236 KB |
Output is correct |
12 |
Correct |
805 ms |
798028 KB |
Output is correct |
13 |
Correct |
705 ms |
796100 KB |
Output is correct |
14 |
Correct |
993 ms |
797904 KB |
Output is correct |
15 |
Correct |
751 ms |
797056 KB |
Output is correct |
16 |
Correct |
906 ms |
797548 KB |
Output is correct |
17 |
Correct |
850 ms |
796316 KB |
Output is correct |
18 |
Correct |
750 ms |
797764 KB |
Output is correct |
19 |
Correct |
767 ms |
798316 KB |
Output is correct |
20 |
Correct |
1184 ms |
798772 KB |
Output is correct |
21 |
Correct |
926 ms |
797068 KB |
Output is correct |
22 |
Correct |
1078 ms |
798500 KB |
Output is correct |
23 |
Correct |
1042 ms |
797000 KB |
Output is correct |
24 |
Correct |
858 ms |
798772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
654 ms |
795256 KB |
Output is correct |
2 |
Correct |
1066 ms |
796880 KB |
Output is correct |
3 |
Correct |
757 ms |
796780 KB |
Output is correct |
4 |
Correct |
996 ms |
796896 KB |
Output is correct |
5 |
Correct |
847 ms |
796008 KB |
Output is correct |
6 |
Correct |
775 ms |
796856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
654 ms |
795256 KB |
Output is correct |
2 |
Correct |
1066 ms |
796880 KB |
Output is correct |
3 |
Correct |
757 ms |
796780 KB |
Output is correct |
4 |
Correct |
996 ms |
796896 KB |
Output is correct |
5 |
Correct |
847 ms |
796008 KB |
Output is correct |
6 |
Correct |
775 ms |
796856 KB |
Output is correct |
7 |
Incorrect |
873 ms |
797412 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |