oj.uz

Submission #428017

# Submission time Handle Problem Language Result Execution time Memory
428017 2021-06-15T07:16:55 Z 송준혁(#7526) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 924 ms 637080 KB 
#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);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory 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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory 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