#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;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
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);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
632780 KB |
Output is correct |
2 |
Correct |
281 ms |
632852 KB |
Output is correct |
3 |
Correct |
273 ms |
632856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
632780 KB |
Output is correct |
2 |
Correct |
281 ms |
632852 KB |
Output is correct |
3 |
Correct |
273 ms |
632856 KB |
Output is correct |
4 |
Correct |
328 ms |
633156 KB |
Output is correct |
5 |
Correct |
288 ms |
633156 KB |
Output is correct |
6 |
Correct |
282 ms |
633120 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
632780 KB |
Output is correct |
2 |
Correct |
281 ms |
632852 KB |
Output is correct |
3 |
Correct |
273 ms |
632856 KB |
Output is correct |
4 |
Correct |
328 ms |
633156 KB |
Output is correct |
5 |
Correct |
288 ms |
633156 KB |
Output is correct |
6 |
Correct |
282 ms |
633120 KB |
Output is correct |
7 |
Correct |
476 ms |
636572 KB |
Output is correct |
8 |
Correct |
765 ms |
636556 KB |
Output is correct |
9 |
Correct |
556 ms |
636496 KB |
Output is correct |
10 |
Correct |
726 ms |
636600 KB |
Output is correct |
11 |
Correct |
584 ms |
636724 KB |
Output is correct |
12 |
Correct |
647 ms |
636560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
632780 KB |
Output is correct |
2 |
Correct |
281 ms |
632852 KB |
Output is correct |
3 |
Correct |
273 ms |
632856 KB |
Output is correct |
4 |
Correct |
328 ms |
633156 KB |
Output is correct |
5 |
Correct |
288 ms |
633156 KB |
Output is correct |
6 |
Correct |
282 ms |
633120 KB |
Output is correct |
7 |
Correct |
483 ms |
636720 KB |
Output is correct |
8 |
Correct |
924 ms |
636948 KB |
Output is correct |
9 |
Correct |
705 ms |
636624 KB |
Output is correct |
10 |
Correct |
805 ms |
636776 KB |
Output is correct |
11 |
Correct |
671 ms |
636728 KB |
Output is correct |
12 |
Correct |
699 ms |
636788 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
300 ms |
632780 KB |
Output is correct |
2 |
Correct |
281 ms |
632852 KB |
Output is correct |
3 |
Correct |
273 ms |
632856 KB |
Output is correct |
4 |
Correct |
328 ms |
633156 KB |
Output is correct |
5 |
Correct |
288 ms |
633156 KB |
Output is correct |
6 |
Correct |
282 ms |
633120 KB |
Output is correct |
7 |
Correct |
476 ms |
636572 KB |
Output is correct |
8 |
Correct |
765 ms |
636556 KB |
Output is correct |
9 |
Correct |
556 ms |
636496 KB |
Output is correct |
10 |
Correct |
726 ms |
636600 KB |
Output is correct |
11 |
Correct |
584 ms |
636724 KB |
Output is correct |
12 |
Correct |
647 ms |
636560 KB |
Output is correct |
13 |
Correct |
483 ms |
636720 KB |
Output is correct |
14 |
Correct |
924 ms |
636948 KB |
Output is correct |
15 |
Correct |
705 ms |
636624 KB |
Output is correct |
16 |
Correct |
805 ms |
636776 KB |
Output is correct |
17 |
Correct |
671 ms |
636728 KB |
Output is correct |
18 |
Correct |
699 ms |
636788 KB |
Output is correct |
19 |
Correct |
556 ms |
636960 KB |
Output is correct |
20 |
Correct |
887 ms |
636948 KB |
Output is correct |
21 |
Correct |
597 ms |
636780 KB |
Output is correct |
22 |
Correct |
758 ms |
636920 KB |
Output is correct |
23 |
Correct |
585 ms |
636896 KB |
Output is correct |
24 |
Correct |
694 ms |
637080 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
463 ms |
636532 KB |
Output is correct |
2 |
Correct |
813 ms |
636504 KB |
Output is correct |
3 |
Correct |
582 ms |
636496 KB |
Output is correct |
4 |
Correct |
727 ms |
636512 KB |
Output is correct |
5 |
Correct |
654 ms |
636588 KB |
Output is correct |
6 |
Correct |
662 ms |
636492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
463 ms |
636532 KB |
Output is correct |
2 |
Correct |
813 ms |
636504 KB |
Output is correct |
3 |
Correct |
582 ms |
636496 KB |
Output is correct |
4 |
Correct |
727 ms |
636512 KB |
Output is correct |
5 |
Correct |
654 ms |
636588 KB |
Output is correct |
6 |
Correct |
662 ms |
636492 KB |
Output is correct |
7 |
Correct |
555 ms |
637052 KB |
Output is correct |
8 |
Correct |
895 ms |
636936 KB |
Output is correct |
9 |
Correct |
645 ms |
636776 KB |
Output is correct |
10 |
Correct |
802 ms |
637044 KB |
Output is correct |
11 |
Correct |
582 ms |
636884 KB |
Output is correct |
12 |
Correct |
727 ms |
636952 KB |
Output is correct |