#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 Seg1{
ll tree[800800], lazy[800800];
void init(int i, int l, int r){
tree[i] = lazy[i] = 0;
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){
tree[i] += lazy[i] * (Y[r+1] - Y[l]);
if (l!=r){
lazy[i<<1] += lazy[i];
lazy[i<<1|1] += lazy[i];
}
lazy[i] = 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){
lazy[i] += x;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, s, e, x); update(i<<1|1, m+1, r, s, e, x);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
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];
int m = (l+r)>>1;
return query(i<<1, l, m, s, e) + query(i<<1|1, m+1, r, 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]);
X.push_back(X3[i]);
X.push_back(X4[i]);
Y.push_back(Y3[i]);
Y.push_back(Y4[i]);
}
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({X1[i], 2, i});
E.push_back({X2[i], 1, i});
}
for (int i=1;i<=q;i++){
X3[i] = getidx(X, X3[i]);
X4[i] = getidx(X, X4[i]);
Y3[i] = getidx(Y, Y3[i]);
Y4[i] = getidx(Y, Y4[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(1, 1, 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(1, 1, sz, Y1[i], Y2[i]-1, X[X2[i]] - X[X1[i]]);
}
else if (op==3 || op==4){
ll S = tree1.query(1, 1, sz, Y3[i], Y4[i]-1);
auto [ofs, cnt] = tree2.query(1, 1, sz, Y3[i], Y4[i]-1);
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:123:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | scanf("%d %d %d %d %d", &r, &c, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | scanf("%lld %lld %lld %lld", X1+i, Y1+i, X2+i, Y2+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:143:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
143 | scanf("%lld %lld %lld %lld %d", X3+i, Y3+i, X4+i, Y4+i, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
25588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
25588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
