#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> vx;
struct segTree{
struct Node{
Node *lc, *rc;
ll a, b, lazyA, lazyB;
Node(){
lc = rc = nullptr;
a = b = lazyA = lazyB = 0;
}
Node(int l, int r){
lc = rc = nullptr;
a = b = lazyA = lazyB = 0;
if(l==r) return;
int m = (l+r)>>1;
lc = new Node(l, m);
rc = new Node(m+1, r);
}
~Node(){
if(lc) delete lc;
if(rc) delete rc;
}
Node *propagate(int l, int r){
Node *tmp = new Node();
*tmp = *this;
tmp->a += lazyA * (vx[r+1] - vx[l]), tmp->b += lazyB * (vx[r+1] - vx[l]);
if(l!=r){
tmp->lc = new Node(); *(tmp->lc) = *lc; tmp->lc->lazyA += lazyA, tmp->lc->lazyB += lazyB;
tmp->rc = new Node(); *(tmp->rc) = *rc; tmp->rc->lazyA += lazyA, tmp->rc->lazyB += lazyB;
}
tmp->lazyA = tmp->lazyB = 0;
return tmp;
}
Node *update(int l, int r, int s, int e, ll av, ll bv){
Node *ret = propagate(l, r);
if(r<s || e<l) return ret;
if(s<=l && r<=e){
ret->lazyA = av, ret->lazyB = bv;
ret = ret->propagate(l, r);
return ret;
}
int m = (l+r)>>1;
ret->lc = lc->update(l, m, s, e, av, bv);
ret->rc = rc->update(m+1, r, s, e, av, bv);
ret->a = ret->lc->a + ret->rc->a, ret->b = ret->lc->b + ret->rc->b;
return ret;
}
pair<Node*, ll> query(int l, int r, int s, int e, ll t){
Node *ret = propagate(l, r);
if(r<s || e<l) return make_pair(ret, 0);
if(s<=l && r<=e) return make_pair(ret, ret->a*t+ret->b);
int m = (l+r)>>1;
ll rn = 0;
pair<Node*, ll> p = ret->lc->query(l, m, s, e, t);
ret->lc = p.first, rn += p.second;
p = ret->rc->query(m+1, r, s, e, t);
ret->rc = p.first, rn += p.second;
return make_pair(ret, rn);
}
} *root;
Node *history[400002]; int historyCnt;
ll times[400002];
int MX;
void init(int maxX){
MX = maxX, historyCnt = 0;
history[historyCnt] = root = new Node(0, MX);
times[historyCnt] = -1e9;
historyCnt++;
}
void update(int s, int e, ll av, ll bv){
root = root->update(0, MX, s, e, av, bv);
}
void step(ll t){
history[historyCnt] = root;
times[historyCnt] = t;
historyCnt++;
}
ll query(int s, int e, ll t){
int idx = upper_bound(times, times+historyCnt, t) - times - 1;
pair<Node*, ll> p = history[idx]->query(0, MX, s, e, t);
history[idx] = p.first;
return p.second;
}
ll query(int s, int e, ll t1, ll t2){
return query(s, e, t2) - query(s, e, t1-1);
}
} tree;
struct Event{
int type; ll y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
Event(){}
Event(int type, ll y, ll l, ll r, ll a, ll b): type(type), y(y), l(l), r(r), a(a), b(b){}
bool operator<(const Event &r)const{
if(y!=r.y) return y<r.y;
return type<r.type;
}
};
int n, q, MOD;
vector<Event> vec;
ll ans[50002];
int main(){
scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
for(int i=1; i<=n; i++){
ll x1, y1, x2, y2;
scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
if(x1>x2) swap(x1, x2);
if(y1>y2) swap(y1, y2);
x1++, y1++;
/// [x1, x2] [y1, y2] ������ ���ϴ� ������ �Է��� �ٲ�
vec.push_back(Event(1, y1, x1, x2, 1, -y1+1));
vec.push_back(Event(0, y2+1, x1, x2, -1, y2));
}
for(Event &p: vec){
vx.push_back(p.l);
vx.push_back(p.r+1);
}
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
for(Event &p: vec){
p.l = lower_bound(vx.begin(), vx.end(), p.l) - vx.begin();
p.r = lower_bound(vx.begin(), vx.end(), p.r+1) - vx.begin() - 1;
}
sort(vec.begin(), vec.end());
const int MX = (int)vx.size() - 2;
tree.init(MX);
for(Event &p: vec){
tree.update(p.l, p.r, p.a, p.b);
tree.step(p.y);
}
ll lastAns = 0;
for(int i=1; i<=q; i++){
ll x1, y1, x2, y2, v;
scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
x1 = (x1 + lastAns * v) % MOD;
x2 = (x2 + lastAns * v) % MOD;
y1 = (y1 + lastAns * v) % MOD;
y2 = (y2 + lastAns * v) % MOD;
if(x1>x2) swap(x1, x2);
if(y1>y2) swap(y1, y2);
x1++, y1++;
x1 = max(x1, vx[0]), x2 = min(x2, vx.back()-1);
if(x1 <= x2){
int idx1 = lower_bound(vx.begin(), vx.end(), x1) - vx.begin();
int idx2 = upper_bound(vx.begin(), vx.end(), x2) - vx.begin() - 1;
lastAns = 0;
if(idx1 > idx2){ /// ���� ��ü�� �ϳ��� ������ ��� ����
int i = idx2;
lastAns = tree.query(i, i, y1, y2) / (vx[i+1] - vx[i]) * (x2-x1+1);
}
else{
if(idx1 < idx2) lastAns = tree.query(idx1, idx2-1, y1, y2);
if(idx1 && x1 < vx[idx1])
lastAns += tree.query(idx1-1, idx1-1, y1, y2) / (vx[idx1] - vx[idx1-1]) * (vx[idx1] - x1);
if(idx2 <= MX && vx[idx2] <= x2)
lastAns += tree.query(idx2, idx2, y1, y2) / (vx[idx2+1] - vx[idx2]) * (x2 - vx[idx2] + 1);
}
}
printf("%lld\n", lastAns);
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
665 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
665 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
