#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];
int sz, szT, szR;
void init(int n){
sz = n;
tree[0] = Node(0, 0, 0, 0, 0);
root[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){
if (r<s || e<l) return;
propagate(i, l, r);
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){
propagate(i, l, r);
if (r<s || e<l) return 0;
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 s, int e, ll x){
update(add(), 1, sz, s, e, x);
}
ll query(int t, int s, int e){
return query(root[t], 1, sz, s, e);
}
}tree1;
struct Node{
ll ofs, cnt;
Node(){}
Node(ll _ofs, ll _cnt): ofs(_ofs), cnt(_cnt) {}
Node operator + (const Node &N) const{
return Node(ofs + N.ofs, cnt + N.cnt);
}
};
struct Seg2{
Node tree[800800], lazy[800800];
void init(int i, int l, int r){
tree[i] = Node(0, 0);
lazy[i] = Node(0, -1);
if (l==r) return;
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
}
void propagate(int i, int l, int r){
if (lazy[i].cnt==-1) return;
if (lazy[i].cnt==0) tree[i] = Node(0, 0);
else tree[i] = Node(lazy[i].ofs * (Y[r+1] - Y[l]), Y[r+1] - Y[l]);
if (l!=r){
lazy[i<<1] = lazy[i];
lazy[i<<1|1] = lazy[i];
}
lazy[i] = Node(0, -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){
lazy[i] = Node(ofs, typ);
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, ofs, typ); update(i<<1|1, m+1, r, s, e, ofs, typ);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
Node query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if (r<s || e<l) return Node(0, 0);
if (s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, 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(1, 1, sz);
for (auto &[x, op, i]:E){
if (op==2){
tree2.update(1, 1, sz, Y1[i], Y2[i]-1, -X[X1[i]], 1);
}
else if (op==1){ // 삭제 먼저
tree2.update(1, 1, sz, Y1[i], Y2[i]-1, 0, 0);
tree1.update(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(tree1.szR-1, l, r-1);
ll tmpl = tree1.query(tree1.szR-1, l, l) / (Y[l+1] - Y[l]);
ll tmpr = tree1.query(tree1.szR-1, 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(1, 1, sz, l, r-1);
auto [ofsl, cntl] = tree2.query(1, 1, sz, l, l);
auto [ofsr, cntr] = tree2.query(1, 1, sz, 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;
}
}
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:167:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
167 | scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
175 | scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:187:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
83840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
246 ms |
83840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
