#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, Q, T;
int num;
LL ans;
struct Node{
int l, r;
int a, x, h, t=-1;
LL s;
} S[20202020];
void upd(int pv, int nw, int s, int e, int ts, int te){
if (e < ts || te < s) return;
if (ts <= s && e <= te){
if (S[nw].t < 0) S[nw].t = S[nw].x = T, S[nw].a = e-s+1;
else{
S[nw].h += T-S[nw].t;
S[nw].s += (LL)(T-S[nw].t)*(e-s+1);
S[nw].a = 0, S[nw].x = T, S[nw].t = -1;
}
return;
}
int m=s+e>>1;
S[nw].l = ++num, S[num] = S[S[pv].l];
S[nw].r = ++num, S[num] = S[S[pv].r];
upd(S[pv].l, S[nw].l, s, m, ts, te);
upd(S[pv].r, S[nw].r, m+1, e, ts, te);
S[nw].s += (LL)S[nw].a * (T-S[nw].x), S[nw].x = T;
S[nw].a = S[S[nw].l].a + S[S[nw].r].a;
}
LL sum(int id, int s, int e, int ts, int te){
if (e < ts || te < s || !id) return 0;
if (ts <= s && e <= te) return S[id].s + (LL)S[id].a*(T-S[id].x);
int m=s+e>>1;
LL r = (min(te, e)-max(ts, s)+1ll)*(S[id].h + (S[id].t<0?0:T-S[id].t));
return sum(S[id].l, s, m, ts, te) + sum(S[id].r, m+1, e, ts, te) + r;
}
vector<pii> P;
struct Event{int x, y1, y2, t;};
vector<Event> E;
int main(){
int x1, y1, x2, y2, v;
scanf("%*d %*d %d %d %d", &N, &Q, &M);
for (int i=1; i<=N; i++){
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
E.pb((Event){x1, y1+1, y2, 1});
E.pb((Event){x2, y1+1, y2, -1});
}
sort(E.begin(), E.end(), [&](Event a, Event b){
if (a.x != b.x) return a.x < b.x;
return a.t < b.t;
});
int u=0;
P.pb(pii(0, 0));
for (Event e : E){
T = e.x;
int nx = ++num;
S[nx] = S[u];
upd(u, nx, 1, MOD+3, e.y1, e.y2);
u = nx;
P.pb(pii(T, u));
}
while (Q--){
ans %= M;
scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
x1 = (x1 + ans*v)%M, y1 = (y1 + ans*v)%M;
x2 = (x2 + ans*v)%M, y2 = (y2 + ans*v)%M;
T = x2;
int k = lb(P.begin(), P.end(), pii(x2+1, -1))-P.begin();
if (k > 0) k--;
T = x2;
ans = sum(P[k].se, 1, MOD+3, y1+1, y2);
k = lb(P.begin(), P.end(), pii(x1+1, -1))-P.begin();
if (k > 0) k--;
T = x1;
ans -= sum(P[k].se, 1, MOD+3, y1+1, y2);
printf("%lld\n", ans);
}
return 0;
}
Compilation message
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:33:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int m=s+e>>1;
| ~^~
Main.cpp: In function 'LL sum(int, int, int, int, int)':
Main.cpp:45:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int m=s+e>>1;
| ~^~
Main.cpp: In function 'int main()':
Main.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
57 | scanf("%*d %*d %d %d %d", &N, &Q, &M);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
632840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
632840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
632840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
632840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
315 ms |
632840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
535 ms |
636260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
535 ms |
636260 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
