#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int INF1 = 1e9 + 100;
ll X1[50050], Y1[50050], X2[50050], Y2[50050];
ll X3[50050], Y3[50050], X4[50050], Y4[50050];
ll ans[50050];
vector<ll> X, Y;
inline int getidx(const vector<ll> &a, ll x){return lower_bound(a.begin(), a.end(), x) - a.begin();}
struct PST1{
struct Node{
ll x, lazy;
int l, r, t;
Node(){}
Node(ll _x, ll _la, int _l, int _r, int _t): x(_x), lazy(_la), l(_l), r(_r), t(_t) {}
};
Node tree[20002000];
int root[200200], X[200200];
int sz, szT, szR;
void init(int n){
sz = n;
tree[0] = Node(0, 0, 0, 0, 0);
root[0] = 0;
X[0] = 0;
szT = szR = 1;
}
int cp(int x, int t){
tree[szT++] = tree[x];
tree[szT-1].t = t;
return szT-1;
}
void propagate(int i, int l, int r){
if (l!=r){
if (tree[tree[i].l].t != tree[i].t) tree[i].l = cp(tree[i].l, tree[i].t);
if (tree[tree[i].r].t != tree[i].t) tree[i].r = cp(tree[i].r, tree[i].t);
}
if (tree[i].lazy==0) return;
tree[i].x += tree[i].lazy * (Y[r+1] - Y[l]);
if (l!=r){
tree[tree[i].l].lazy += tree[i].lazy;
tree[tree[i].r].lazy += tree[i].lazy;
}
tree[i].lazy = 0;
}
void update(int i, int l, int r, int s, int e, ll x){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
tree[i].lazy += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(tree[i].l, l, m, s, e, x);
update(tree[i].r, m+1, r, s, e, x);
tree[i].x = tree[tree[i].l].x + tree[tree[i].r].x;
}
ll query(int i, int l, int r, int s, int e){
if (r<s || e<l) return 0;
propagate(i, l, r);
if (s<=l && r<=e){
return tree[i].x;
}
int m = (l+r)>>1;
return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
}
int add(){
root[szR] = cp(root[szR-1], szR);
szR++;
return root[szR-1];
}
void update(int t, int s, int e, ll x){
X[szR] = t;
update(add(), 1, sz, s, e, x);
}
ll query(int t, int s, int e){
t = upper_bound(X+1, X+szR, t) - X - 1;
return query(root[t], 1, sz, s, e);
}
}tree1;
pair<ll, ll> operator + (const pair<ll, ll> &a, const pair<ll, ll> &b){return {a.first + b.first, a.second + b.second};}
struct PST2{
struct Node{
ll ofs, cnt;
ll lazyofs;
int lazycnt, l, r, t;
Node(){}
Node(ll _ofs, ll _cnt, ll _lofs, int _lcnt, int _l, int _r, int _t): ofs(_ofs), cnt(_cnt), lazyofs(_lofs), lazycnt(_lcnt), l(_l), r(_r), t(_t) {}
};
Node tree[20002000];
int root[200200], X[200200];
int sz, szT, szR;
void init(int n){
sz = n;
tree[0] = Node(0, 0, 0, -1, 0, 0, 0);
root[0] = 0;
X[0] = -INF1;
szT = szR = 1;
}
int cp(int x, int t){
tree[szT++] = tree[x];
tree[szT-1].t = t;
return szT-1;
}
void propagate(int i, int l, int r){
if (l!=r){
if (tree[tree[i].l].t != tree[i].t) tree[i].l = cp(tree[i].l, tree[i].t);
if (tree[tree[i].r].t != tree[i].t) tree[i].r = cp(tree[i].r, tree[i].t);
}
if (tree[i].lazycnt==-1) return;
if (tree[i].lazycnt==0) tree[i].ofs = 0, tree[i].cnt = 0;
else tree[i].ofs = tree[i].lazyofs * (Y[r+1]-Y[l]), tree[i].cnt = Y[r+1] - Y[l];
if (l!=r){
tree[tree[i].l].lazycnt = tree[i].lazycnt;
tree[tree[i].l].lazyofs = tree[i].lazyofs;
tree[tree[i].r].lazycnt = tree[i].lazycnt;
tree[tree[i].r].lazyofs = tree[i].lazyofs;
}
tree[i].lazyofs = 0;
tree[i].lazycnt = -1;
}
void update(int i, int l, int r, int s, int e, ll ofs, int typ){
propagate(i, l, r);
if (r<s || e<l) return;
if (s<=l && r<=e){
tree[i].lazyofs = ofs;
tree[i].lazycnt = typ;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(tree[i].l, l, m, s, e, ofs, typ);
update(tree[i].r, m+1, r, s, e, ofs, typ);
tree[i].ofs = tree[tree[i].l].ofs + tree[tree[i].r].ofs;
tree[i].cnt = tree[tree[i].l].cnt + tree[tree[i].r].cnt;
}
pair<ll, ll> query(int i, int l, int r, int s, int e){
if (r<s || e<l) return {0, 0};
propagate(i, l, r);
if (s<=l && r<=e){
return {tree[i].ofs, tree[i].cnt};
}
int m = (l+r)>>1;
return query(tree[i].l, l, m, s, e) + query(tree[i].r, m+1, r, s, e);
}
int add(){
root[szR] = cp(root[szR-1], szR);
szR++;
return root[szR-1];
}
void update(int t, int s, int e, ll ofs, int typ){
X[szR] = t;
update(add(), 1, sz, s, e, ofs, typ);
}
pair<ll, ll> query(int t, int s, int e){
t = upper_bound(X+1, X+szR, t) - X - 1;
return query(root[t], 1, sz, s, e);
}
}tree2;
int main(){
int r, c, n, q, MOD;
scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
X.push_back(-INF1);
X.push_back(INF1);
Y.push_back(-INF1);
Y.push_back(INF1);
for (int i=1;i<=n;i++){
scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
if (X1[i] > X2[i]) swap(X1[i], X2[i]);
if (Y1[i] > Y2[i]) swap(Y1[i], Y2[i]);
X.push_back(X1[i]);
X.push_back(X2[i]);
Y.push_back(Y1[i]);
Y.push_back(Y2[i]);
}
// for (int i=1;i<=q;i++){
// int v;
// scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
// X3[i] %= MOD;
// X4[i] %= MOD;
// Y3[i] %= MOD;
// Y4[i] %= MOD;
// if (X3[i] > X4[i]) swap(X3[i], X4[i]);
// if (Y3[i] > Y4[i]) swap(Y3[i], Y4[i]);
// }
// auto rans = naive(n, q);
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
sort(Y.begin(), Y.end());
Y.erase(unique(Y.begin(), Y.end()), Y.end());
vector<array<ll, 3>> E;
for (int i=1;i<=n;i++){
X1[i] = getidx(X, X1[i]);
X2[i] = getidx(X, X2[i]);
Y1[i] = getidx(Y, Y1[i]);
Y2[i] = getidx(Y, Y2[i]);
if (X1[i]==X2[i]) continue;
E.push_back({X[X1[i]], 2, i});
E.push_back({X[X2[i]], 1, i});
}
// for (int i=1;i<=q;i++){
// E.push_back({X3[i], 3, i});
// E.push_back({X4[i], 4, i});
// }
sort(E.begin(), E.end());
int sz = (int)Y.size()-2;
assert(sz >= 1);
tree1.init(sz);
tree2.init(sz);
for (auto &[x, op, i]:E){
if (op==2){
tree2.update(x, Y1[i], Y2[i]-1, -X[X1[i]], 1);
}
else if (op==1){ // 삭제 먼저
tree2.update(x, Y1[i], Y2[i]-1, 0, 0);
tree1.update(x, Y1[i], Y2[i]-1, X[X2[i]] - X[X1[i]]);
}
// else if (op==3 || op==4){
// int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
// int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();
// ll S = tree1.query(x, l, r-1);
// ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
// ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
// S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);
// auto [ofs, cnt] = tree2.query(x, l, r-1);
// auto [ofsl, cntl] = tree2.query(x, l, l);
// auto [ofsr, cntr] = tree2.query(x, r-1, r-1);
// ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
// ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);
// ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
// ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);
// if (op==3) S += cnt * X3[i] + ofs;
// else S += cnt * X4[i] + ofs;
// if (op==3) S = -S;
// ans[i] += S;
// }
}
ll pans = 0;
for (int i=1;i<=q;i++){
int v;
scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
pans %= MOD;
X3[i] = (X3[i] + pans * v) % MOD;
X4[i] = (X4[i] + pans * v) % MOD;
Y3[i] = (Y3[i] + pans * v) % MOD;
Y4[i] = (Y4[i] + pans * v) % MOD;
if (X3[i] > X4[i]) swap(X3[i], X4[i]);
if (Y3[i] > Y4[i]) swap(Y3[i], Y4[i]);
{
int op = 3;
int x = X3[i];
int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();
ll S = tree1.query(x, l, r-1);
ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);
auto [ofs, cnt] = tree2.query(x, l, r-1);
auto [ofsl, cntl] = tree2.query(x, l, l);
auto [ofsr, cntr] = tree2.query(x, r-1, r-1);
ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);
ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);
if (op==3) S += cnt * X3[i] + ofs;
else S += cnt * X4[i] + ofs;
if (op==3) S = -S;
ans[i] += S;
}
{
int op = 4;
int x = X4[i];
int l = upper_bound(Y.begin(), Y.end(), Y3[i]) - Y.begin() - 1;
int r = lower_bound(Y.begin(), Y.end(), Y4[i]) - Y.begin();
ll S = tree1.query(x, l, r-1);
ll tmpl = tree1.query(x, l, l) / (Y[l+1] - Y[l]);
ll tmpr = tree1.query(x, r-1, r-1) / (Y[r] - Y[r-1]);
S += tmpl * (-Y3[i] + Y[l]) + tmpr * (-Y[r] + Y4[i]);
auto [ofs, cnt] = tree2.query(x, l, r-1);
auto [ofsl, cntl] = tree2.query(x, l, l);
auto [ofsr, cntr] = tree2.query(x, r-1, r-1);
ofsl /= (Y[l+1] - Y[l]), cntl /= (Y[l+1] - Y[l]);
ofsr /= (Y[r] - Y[r-1]), cntr /= (Y[r] - Y[r-1]);
ofs += ofsl * (-Y3[i] + Y[l]), cnt += cntl * (-Y3[i] + Y[l]);
ofs += ofsr * (-Y[r] + Y4[i]), cnt += cntr * (-Y[r] + Y4[i]);
if (op==3) S += cnt * X3[i] + ofs;
else S += cnt * X4[i] + ofs;
if (op==3) S = -S;
ans[i] += S;
}
pans = ans[i];
}
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:210:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
210 | scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:218:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
218 | scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:312:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
312 | scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3540 KB |
Output is correct |
2 |
Correct |
4 ms |
3796 KB |
Output is correct |
3 |
Correct |
4 ms |
3796 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3540 KB |
Output is correct |
2 |
Correct |
4 ms |
3796 KB |
Output is correct |
3 |
Correct |
4 ms |
3796 KB |
Output is correct |
4 |
Correct |
84 ms |
58416 KB |
Output is correct |
5 |
Correct |
68 ms |
52508 KB |
Output is correct |
6 |
Correct |
84 ms |
56884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3540 KB |
Output is correct |
2 |
Correct |
4 ms |
3796 KB |
Output is correct |
3 |
Correct |
4 ms |
3796 KB |
Output is correct |
4 |
Correct |
84 ms |
58416 KB |
Output is correct |
5 |
Correct |
68 ms |
52508 KB |
Output is correct |
6 |
Correct |
84 ms |
56884 KB |
Output is correct |
7 |
Correct |
585 ms |
352696 KB |
Output is correct |
8 |
Correct |
1417 ms |
895836 KB |
Output is correct |
9 |
Correct |
870 ms |
758236 KB |
Output is correct |
10 |
Correct |
1364 ms |
888072 KB |
Output is correct |
11 |
Correct |
1047 ms |
742116 KB |
Output is correct |
12 |
Correct |
1290 ms |
845308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3540 KB |
Output is correct |
2 |
Correct |
4 ms |
3796 KB |
Output is correct |
3 |
Correct |
4 ms |
3796 KB |
Output is correct |
4 |
Correct |
84 ms |
58416 KB |
Output is correct |
5 |
Correct |
68 ms |
52508 KB |
Output is correct |
6 |
Correct |
84 ms |
56884 KB |
Output is correct |
7 |
Correct |
446 ms |
339668 KB |
Output is correct |
8 |
Correct |
1609 ms |
884712 KB |
Output is correct |
9 |
Correct |
834 ms |
746712 KB |
Output is correct |
10 |
Correct |
1235 ms |
875852 KB |
Output is correct |
11 |
Correct |
956 ms |
737496 KB |
Output is correct |
12 |
Correct |
1177 ms |
807940 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
3540 KB |
Output is correct |
2 |
Correct |
4 ms |
3796 KB |
Output is correct |
3 |
Correct |
4 ms |
3796 KB |
Output is correct |
4 |
Correct |
84 ms |
58416 KB |
Output is correct |
5 |
Correct |
68 ms |
52508 KB |
Output is correct |
6 |
Correct |
84 ms |
56884 KB |
Output is correct |
7 |
Correct |
585 ms |
352696 KB |
Output is correct |
8 |
Correct |
1417 ms |
895836 KB |
Output is correct |
9 |
Correct |
870 ms |
758236 KB |
Output is correct |
10 |
Correct |
1364 ms |
888072 KB |
Output is correct |
11 |
Correct |
1047 ms |
742116 KB |
Output is correct |
12 |
Correct |
1290 ms |
845308 KB |
Output is correct |
13 |
Correct |
446 ms |
339668 KB |
Output is correct |
14 |
Correct |
1609 ms |
884712 KB |
Output is correct |
15 |
Correct |
834 ms |
746712 KB |
Output is correct |
16 |
Correct |
1235 ms |
875852 KB |
Output is correct |
17 |
Correct |
956 ms |
737496 KB |
Output is correct |
18 |
Correct |
1177 ms |
807940 KB |
Output is correct |
19 |
Correct |
537 ms |
488840 KB |
Output is correct |
20 |
Correct |
1406 ms |
908256 KB |
Output is correct |
21 |
Correct |
812 ms |
744276 KB |
Output is correct |
22 |
Correct |
1284 ms |
898668 KB |
Output is correct |
23 |
Correct |
1014 ms |
747972 KB |
Output is correct |
24 |
Correct |
1186 ms |
829844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
341 ms |
325524 KB |
Output is correct |
2 |
Correct |
1371 ms |
866512 KB |
Output is correct |
3 |
Correct |
880 ms |
783020 KB |
Output is correct |
4 |
Correct |
1287 ms |
864432 KB |
Output is correct |
5 |
Correct |
1046 ms |
732732 KB |
Output is correct |
6 |
Correct |
1250 ms |
850912 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
341 ms |
325524 KB |
Output is correct |
2 |
Correct |
1371 ms |
866512 KB |
Output is correct |
3 |
Correct |
880 ms |
783020 KB |
Output is correct |
4 |
Correct |
1287 ms |
864432 KB |
Output is correct |
5 |
Correct |
1046 ms |
732732 KB |
Output is correct |
6 |
Correct |
1250 ms |
850912 KB |
Output is correct |
7 |
Correct |
574 ms |
488944 KB |
Output is correct |
8 |
Correct |
1431 ms |
914720 KB |
Output is correct |
9 |
Correct |
837 ms |
746952 KB |
Output is correct |
10 |
Correct |
1361 ms |
905300 KB |
Output is correct |
11 |
Correct |
1002 ms |
756104 KB |
Output is correct |
12 |
Correct |
1291 ms |
835348 KB |
Output is correct |