#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
vector<ll> xVec, yVec;
struct xNode {
struct yNode {
ll globalSum, globalLazy;
ll totalSum, totalLazy;
yNode *lchild, *rchild;
yNode(){
globalSum = globalLazy = totalSum = totalLazy = 0;
lchild = rchild = nullptr;
}
~yNode(){
if(lchild) delete lchild;
if(rchild) delete rchild;
}
void update(int l, int r, int s, int e, ll bonus, ll len, bool same){
if(l==s && r==e){
if(same){
globalSum += 1 * (yVec[e] - yVec[s]);
globalLazy += 1;
}
totalSum += len * (yVec[e] - yVec[s]);
totalLazy += len;
return;
}
int m = (l+r)/2;
if(s<m){
if(!lchild) lchild = new yNode();
lchild->update(l, m, s, min(m, e), bonus, len, same);
}
if(m<e){
if(!rchild) rchild = new yNode();
rchild->update(m, r, max(s, m), e, bonus, len, same);
}
if(same){
globalSum = (lchild ? lchild->globalSum : 0) + (rchild ? rchild->globalSum : 0) + globalLazy * (yVec[r] - yVec[l]);
}
totalSum = (lchild ? lchild->totalSum : 0) + (rchild ? rchild->totalSum : 0) + totalLazy * (yVec[r] - yVec[l]);
}
};
yNode *tree;
xNode *lchild, *rchild;
xNode(){
tree = nullptr;
lchild = rchild = nullptr;
}
~xNode(){
if(tree) delete tree;
if(lchild) delete lchild;
if(rchild) delete rchild;
}
void update(int xl, int xr, int yl, int yr, int xs, int xe, int ys, int ye){
ll len = xVec[xe] - xVec[xs];
if(xl != xs || xr != xe){
int m = (xl+xr)/2;
if(xs < m){
if(!lchild) lchild = new xNode();
lchild->update(xl, m, yl, yr, xs, min(m, xe), ys, ye);
}
if(m < xe){
if(!rchild) rchild = new xNode();
rchild->update(m, xr, yl, yr, max(xs, m), xe, ys, ye);
}
}
if(!tree) tree = new yNode();
tree->update(yl, yr, ys, ye, xVec[xr] - xVec[xl], len, xl==xs && xr==xe);
}
} *tree;
ll query(xNode::yNode *i, int l, int r, int s, int e, ll lazySum, ll len, bool same){
ll ret = 0;
if(l==s && r==e){
if(same){
if(i) ret += i->totalSum;
ret += lazySum * (yVec[r] - yVec[l]);
}
else{
if(i) ret += i->globalSum * len;
ret += lazySum * len * (yVec[r] - yVec[l]);
}
return ret;
}
lazySum = !i ? lazySum : (lazySum + (same ? i->totalLazy : i->globalLazy));
int m = (l+r)/2;
if(s<m) ret += query(i ? i->lchild : nullptr, l, m, s, min(m, e), lazySum, len, same);
if(m<e) ret += query(i ? i->rchild : nullptr, m, r, max(s, m), e, lazySum, len, same);
return ret;
}
ll query(xNode *i, int xl, int xr, int yl, int yr, int xs, int xe, int ys, int ye){
ll len = xVec[xe] - xVec[xs];
ll ret = query(i->tree, yl, yr, ys, ye, 0, len, xl==xs && xr==xe);
if(xl!=xs || xr!=xe){
int m = (xl+xr)/2;
if(xs<m && i->lchild) ret += query(i->lchild, xl, m, yl, yr, xs, min(m, xe), ys, ye);
if(m<xe && i->rchild) ret += query(i->rchild, m, xr, yl, yr, max(xs, m), xe, ys, ye);
}
return ret;
}
int r, c, n, q, m, N, M;
ll _x1[50002], _y1[50002], _x2[50002], _y2[50002];
ll query(int xs, int xe, int ys, int ye){
return query(tree, 0, N-1, 0, M-1, xs, xe, ys, ye);
}
int main(){
scanf("%d %d %d %d %d", &r, &c, &n, &q, &m);
xVec.push_back(0), xVec.push_back(r);
yVec.push_back(0), yVec.push_back(c);
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]);
xVec.push_back(_x1[i]), xVec.push_back(_x2[i]);
yVec.push_back(_y1[i]), yVec.push_back(_y2[i]);
}
sort(xVec.begin(), xVec.end());
xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
sort(yVec.begin(), yVec.end());
yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
N = (int)xVec.size(), M = (int)yVec.size();
tree = new xNode();
for(int i=1; i<=n; i++){
_x1[i] = lower_bound(xVec.begin(), xVec.end(), _x1[i]) - xVec.begin();
_x2[i] = lower_bound(xVec.begin(), xVec.end(), _x2[i]) - xVec.begin();
_y1[i] = lower_bound(yVec.begin(), yVec.end(), _y1[i]) - yVec.begin();
_y2[i] = lower_bound(yVec.begin(), yVec.end(), _y2[i]) - yVec.begin();
tree->update(0, N-1, 0, M-1, _x1[i], _x2[i], _y1[i], _y2[i]);
}
if(n>5000 || q>5000) return 0;
ll ans = 0;
for(int i=1; i<=q; i++){
ll qx1, qy1, qx2, qy2, v;
scanf("%lld %lld %lld %lld %lld", &qx1, &qy1, &qx2, &qy2, &v);
ans %= m, v %= m;
qx1 = (qx1 + ans * v) % m;
qx2 = (qx2 + ans * v) % m;
qy1 = (qy1 + ans * v) % m;
qy2 = (qy2 + ans * v) % m;
if(qx1 > qx2) swap(qx1, qx2);
if(qy1 > qy2) swap(qy1, qy2);
int xl = upper_bound(xVec.begin(), xVec.end(), qx1) - xVec.begin() - 1;
int xr = lower_bound(xVec.begin(), xVec.end(), qx2) - xVec.begin();
int yl = upper_bound(yVec.begin(), yVec.end(), qy1) - yVec.begin() - 1;
int yr = lower_bound(yVec.begin(), yVec.end(), qy2) - yVec.begin();
bool xSingle = (xr-xl == 1);
bool ySingle = (yr-yl == 1);
ans = 0;
if(xSingle && ySingle){
ans = !!query(xl, xr, yl, yr) * (qx2 - qx1) * (qy2 - qy1);
}
else if(xSingle){
ans = query(xl, xr, yl+1, yr-1) / (xVec[xr] - xVec[xl]) * (qx2 - qx1);
ans += !!query(xl, xr, yl, yl+1) * (qx2 - qx1) * (yVec[yl+1] - qy1);
ans += !!query(xl, xr, yr-1, yr) * (qx2 - qx1) * (qy2 - yVec[yr-1]);
}
else if(ySingle){
ans = query(xl+1, xr-1, yl, yr) / (yVec[yr] - yVec[yl]) * (qy2 - qy1);
ans += !!query(xl, xl+1, yl, yr) * (qy2 - qy1) * (xVec[xl+1] - qx1);
ans += !!query(xr-1, xr, yl, yr) * (qy2 - qy1) * (qx2 - xVec[xr-1]);
}
else{
ans += query(xl+1, xr-1, yl+1, yr-1); /// Center
ans += query(xl+1, xr-1, yl, yl+1) / (yVec[yl+1] - yVec[yl]) * (yVec[yl+1] - qy1); /// Left
ans += query(xl+1, xr-1, yr-1, yr) / (yVec[yr] - yVec[yr-1]) * (qy2 - yVec[yr-1]); /// Right
ans += query(xl, xl+1, yl+1, yr-1) / (xVec[xl+1] - xVec[xl]) * (xVec[xl+1] - qx1); /// Down
ans += query(xr-1, xr, yl+1, yr-1) / (xVec[xr] - xVec[xr-1]) * (qx2 - xVec[xr-1]); /// Up
ans += !!query(xl, xl+1, yl, yl+1) * (xVec[xl+1] - qx1) * (yVec[yl+1] - qy1);
ans += !!query(xl, xl+1, yr-1, yr) * (xVec[xl+1] - qx1) * (qy2 - yVec[yr-1]);
ans += !!query(xr-1, xr, yl, yl+1) * (qx2 - xVec[xr-1]) * (yVec[yl+1] - qy1);
ans += !!query(xr-1, xr, yr-1, yr) * (qx2 - xVec[xr-1]) * (qy2 - yVec[yr-1]);
}
printf("%lld\n", ans);
}
delete tree;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%d %d %d %d %d", &r, &c, &n, &q, &m);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:128:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%lld %lld %lld %lld", &_x1[i], &_y1[i], &_x2[i], &_y2[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:153:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%lld %lld %lld %lld %lld", &qx1, &qy1, &qx2, &qy2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
410 ms |
51472 KB |
Output is correct |
| 5 |
Correct |
360 ms |
35192 KB |
Output is correct |
| 6 |
Correct |
403 ms |
32648 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
410 ms |
51472 KB |
Output is correct |
| 5 |
Correct |
360 ms |
35192 KB |
Output is correct |
| 6 |
Correct |
403 ms |
32648 KB |
Output is correct |
| 7 |
Incorrect |
947 ms |
254704 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
410 ms |
51472 KB |
Output is correct |
| 5 |
Correct |
360 ms |
35192 KB |
Output is correct |
| 6 |
Correct |
403 ms |
32648 KB |
Output is correct |
| 7 |
Incorrect |
2058 ms |
675072 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
2548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
2480 KB |
Output is correct |
| 3 |
Correct |
12 ms |
2252 KB |
Output is correct |
| 4 |
Correct |
410 ms |
51472 KB |
Output is correct |
| 5 |
Correct |
360 ms |
35192 KB |
Output is correct |
| 6 |
Correct |
403 ms |
32648 KB |
Output is correct |
| 7 |
Incorrect |
947 ms |
254704 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
637 ms |
150092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
637 ms |
150092 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
