답안 #676506

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
676506	2022-12-31T03:53:40 Z	penguin133	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	806 ms	118076 KB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, k, q;
int pos[200005], P[200005], L[200005], R[200005], vis[200005];
const int mod = 1e9  +7;
struct node{
	int s,e,m,val,lazy;
	node *l = nullptr, *r = nullptr;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = lazy =0 ;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void propo(){
		if(lazy){
			val = lazy;
			if(s != e)l->lazy = lazy, r->lazy = lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b,int c){
		if(s == a && e == b)lazy = c;
		else{
			if(b <= m)l->upd(a,b,c);
			else if(a > m)r->upd(a,b,c);
			else l->upd(a,m,c), r->upd(m+1,b,c);
			l->propo(), r->propo();
			val = max(l->val, r->val);
		}
	}
	int query(int a, int b){
		propo();
		if(l == nullptr || (s == a && e == b))return val;
		if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a,b);
		else return max(l->query(a,m ), r->query(m+1, b));
	}
}*root;
int ft[200005];
void upd(int l, int r, int v){
	r++;
	for(;r<=n;r+=(r & -r))ft[r] -= v;
	for(;l<=n;l+=(l& -l))ft[l] += v;
}
int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}
pii Q[200005];
//int ans[200005];
pi dis[200005];
pi A[400005];
int par[200005][20];
vector<int>v[200005];

void dfs(int x, int p){
	par[x][0] = p;
	for(auto i : v[x])dfs(i, x);
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> L[i] >> R[i];
		A[i] = {L[i], i}, A[n+i] = {R[i], i};
	}
	sort(A+1, A+2*n+1);
	root = new node(1, 2*n+1);
	int cnt = 0;
	for(int i=1;i<=2*n;i++){
		if(A[i].fi != A[i-1].fi)cnt++;
		if(dis[A[i].se].fi)dis[A[i].se].se = cnt;
		else dis[A[i].se].fi = cnt;
	}
	for(int i=1;i<=n;i++){
		pos[i] = root->query(dis[i].fi, dis[i].se);
		pos[i] = max(pos[i], pos[i-1]);
		root->upd(dis[i].fi, dis[i].se, i);
		v[pos[i]].push_back(i);
	}
	dfs(0, -1);
	for(int i=1;i<=19;i++){
		for(int j=0;j<=n;j++)par[j][i] = par[par[j][i-1]][i-1];
	}
	cin >> q;
	while(q--){
		int x,y;
		cin >> x >> y;
		int ans = 0;
		for(int i=19;i>=0;i--){
			if(par[y][i] >= x)y = par[y][i], ans += (1<<i);
		}
		cout << 1+ans << '\n';
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message

Main.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main(){
      | ^~~~

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	538 ms	108300 KB	Output is correct
2	Correct	539 ms	106956 KB	Output is correct
3	Correct	569 ms	107180 KB	Output is correct
4	Correct	549 ms	108348 KB	Output is correct
5	Correct	597 ms	112816 KB	Output is correct
6	Correct	202 ms	105364 KB	Output is correct
7	Correct	177 ms	104112 KB	Output is correct
8	Correct	191 ms	103892 KB	Output is correct
9	Correct	194 ms	105164 KB	Output is correct
10	Correct	202 ms	100836 KB	Output is correct
11	Correct	326 ms	103188 KB	Output is correct
12	Correct	288 ms	97300 KB	Output is correct
13	Correct	307 ms	96996 KB	Output is correct
14	Correct	312 ms	103540 KB	Output is correct
15	Correct	322 ms	100948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	195 ms	112276 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7748 KB	Output is correct
2	Correct	11 ms	7620 KB	Output is correct
3	Correct	11 ms	7600 KB	Output is correct
4	Correct	12 ms	7684 KB	Output is correct
5	Correct	11 ms	7508 KB	Output is correct
6	Correct	8 ms	7876 KB	Output is correct
7	Correct	8 ms	7636 KB	Output is correct
8	Correct	8 ms	7636 KB	Output is correct
9	Correct	8 ms	7508 KB	Output is correct
10	Correct	8 ms	7508 KB	Output is correct
11	Correct	8 ms	7636 KB	Output is correct
12	Correct	8 ms	7508 KB	Output is correct
13	Correct	8 ms	7496 KB	Output is correct
14	Correct	8 ms	7576 KB	Output is correct
15	Correct	8 ms	7508 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	8 ms	7728 KB	Output is correct

Subtask #3

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	7748 KB	Output is correct
2	Correct	11 ms	7620 KB	Output is correct
3	Correct	11 ms	7600 KB	Output is correct
4	Correct	12 ms	7684 KB	Output is correct
5	Correct	11 ms	7508 KB	Output is correct
6	Correct	8 ms	7876 KB	Output is correct
7	Correct	8 ms	7636 KB	Output is correct
8	Correct	8 ms	7636 KB	Output is correct
9	Correct	8 ms	7508 KB	Output is correct
10	Correct	8 ms	7508 KB	Output is correct
11	Correct	8 ms	7636 KB	Output is correct
12	Correct	8 ms	7508 KB	Output is correct
13	Correct	8 ms	7496 KB	Output is correct
14	Correct	8 ms	7576 KB	Output is correct
15	Correct	8 ms	7508 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	8 ms	7728 KB	Output is correct
18	Correct	75 ms	10372 KB	Output is correct
19	Correct	70 ms	9968 KB	Output is correct
20	Correct	73 ms	10376 KB	Output is correct
21	Correct	74 ms	10064 KB	Output is correct
22	Correct	74 ms	10048 KB	Output is correct
23	Correct	67 ms	10208 KB	Output is correct
24	Correct	70 ms	10188 KB	Output is correct
25	Correct	81 ms	10088 KB	Output is correct
26	Correct	66 ms	10180 KB	Output is correct
27	Correct	74 ms	9940 KB	Output is correct
28	Correct	50 ms	9548 KB	Output is correct
29	Correct	54 ms	9636 KB	Output is correct
30	Correct	52 ms	9584 KB	Output is correct
31	Correct	50 ms	9420 KB	Output is correct
32	Correct	53 ms	9624 KB	Output is correct
33	Correct	3 ms	4948 KB	Output is correct
34	Correct	58 ms	9956 KB	Output is correct

Subtask #4

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	609 ms	113208 KB	Output is correct
2	Correct	628 ms	110956 KB	Output is correct
3	Correct	554 ms	103624 KB	Output is correct
4	Correct	518 ms	102856 KB	Output is correct
5	Correct	539 ms	105552 KB	Output is correct
6	Correct	204 ms	106272 KB	Output is correct
7	Correct	176 ms	102320 KB	Output is correct
8	Correct	201 ms	102196 KB	Output is correct
9	Correct	201 ms	100108 KB	Output is correct
10	Correct	205 ms	106736 KB	Output is correct
11	Correct	320 ms	96404 KB	Output is correct
12	Correct	332 ms	105284 KB	Output is correct
13	Correct	306 ms	96360 KB	Output is correct
14	Correct	308 ms	99240 KB	Output is correct
15	Correct	318 ms	104896 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	219 ms	107752 KB	Output is correct

Subtask #5

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	538 ms	108300 KB	Output is correct
2	Correct	539 ms	106956 KB	Output is correct
3	Correct	569 ms	107180 KB	Output is correct
4	Correct	549 ms	108348 KB	Output is correct
5	Correct	597 ms	112816 KB	Output is correct
6	Correct	202 ms	105364 KB	Output is correct
7	Correct	177 ms	104112 KB	Output is correct
8	Correct	191 ms	103892 KB	Output is correct
9	Correct	194 ms	105164 KB	Output is correct
10	Correct	202 ms	100836 KB	Output is correct
11	Correct	326 ms	103188 KB	Output is correct
12	Correct	288 ms	97300 KB	Output is correct
13	Correct	307 ms	96996 KB	Output is correct
14	Correct	312 ms	103540 KB	Output is correct
15	Correct	322 ms	100948 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	195 ms	112276 KB	Output is correct
18	Correct	11 ms	7748 KB	Output is correct
19	Correct	11 ms	7620 KB	Output is correct
20	Correct	11 ms	7600 KB	Output is correct
21	Correct	12 ms	7684 KB	Output is correct
22	Correct	11 ms	7508 KB	Output is correct
23	Correct	8 ms	7876 KB	Output is correct
24	Correct	8 ms	7636 KB	Output is correct
25	Correct	8 ms	7636 KB	Output is correct
26	Correct	8 ms	7508 KB	Output is correct
27	Correct	8 ms	7508 KB	Output is correct
28	Correct	8 ms	7636 KB	Output is correct
29	Correct	8 ms	7508 KB	Output is correct
30	Correct	8 ms	7496 KB	Output is correct
31	Correct	8 ms	7576 KB	Output is correct
32	Correct	8 ms	7508 KB	Output is correct
33	Correct	3 ms	4948 KB	Output is correct
34	Correct	8 ms	7728 KB	Output is correct
35	Correct	75 ms	10372 KB	Output is correct
36	Correct	70 ms	9968 KB	Output is correct
37	Correct	73 ms	10376 KB	Output is correct
38	Correct	74 ms	10064 KB	Output is correct
39	Correct	74 ms	10048 KB	Output is correct
40	Correct	67 ms	10208 KB	Output is correct
41	Correct	70 ms	10188 KB	Output is correct
42	Correct	81 ms	10088 KB	Output is correct
43	Correct	66 ms	10180 KB	Output is correct
44	Correct	74 ms	9940 KB	Output is correct
45	Correct	50 ms	9548 KB	Output is correct
46	Correct	54 ms	9636 KB	Output is correct
47	Correct	52 ms	9584 KB	Output is correct
48	Correct	50 ms	9420 KB	Output is correct
49	Correct	53 ms	9624 KB	Output is correct
50	Correct	3 ms	4948 KB	Output is correct
51	Correct	58 ms	9956 KB	Output is correct
52	Correct	609 ms	113208 KB	Output is correct
53	Correct	628 ms	110956 KB	Output is correct
54	Correct	554 ms	103624 KB	Output is correct
55	Correct	518 ms	102856 KB	Output is correct
56	Correct	539 ms	105552 KB	Output is correct
57	Correct	204 ms	106272 KB	Output is correct
58	Correct	176 ms	102320 KB	Output is correct
59	Correct	201 ms	102196 KB	Output is correct
60	Correct	201 ms	100108 KB	Output is correct
61	Correct	205 ms	106736 KB	Output is correct
62	Correct	320 ms	96404 KB	Output is correct
63	Correct	332 ms	105284 KB	Output is correct
64	Correct	306 ms	96360 KB	Output is correct
65	Correct	308 ms	99240 KB	Output is correct
66	Correct	318 ms	104896 KB	Output is correct
67	Correct	3 ms	4948 KB	Output is correct
68	Correct	219 ms	107752 KB	Output is correct
69	Correct	751 ms	109096 KB	Output is correct
70	Correct	806 ms	114824 KB	Output is correct
71	Correct	734 ms	106044 KB	Output is correct
72	Correct	766 ms	111784 KB	Output is correct
73	Correct	785 ms	109980 KB	Output is correct
74	Correct	437 ms	118076 KB	Output is correct
75	Correct	398 ms	106952 KB	Output is correct
76	Correct	430 ms	114268 KB	Output is correct
77	Correct	397 ms	104544 KB	Output is correct
78	Correct	370 ms	104932 KB	Output is correct
79	Correct	438 ms	107568 KB	Output is correct
80	Correct	379 ms	100000 KB	Output is correct
81	Correct	373 ms	99320 KB	Output is correct
82	Correct	397 ms	105080 KB	Output is correct
83	Correct	360 ms	100488 KB	Output is correct
84	Correct	3 ms	4948 KB	Output is correct
85	Correct	300 ms	109692 KB	Output is correct