답안 #901074

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
901074	2024-01-09T06:43:34 Z	LCJLY	Event Hopping (BOI22_events)	C++14	100 / 100	463 ms	324816 KB

events

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;

inline pii combine(pii a, pii b){
	if(a.first<b.first) return a;
	return b;
}

struct node{
	int s,e,m;
	node *l,*r;
	pii v;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v({INT_MAX,INT_MAX}){
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void upd(int x, pii y){
		if(s==e){
			if(y.first<v.first){
				v=y;
			}
			return;
		}
		inst();
		if(x<=m)l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	pii query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		inst();
		if(y<=m)return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

void solve(){	
	int n,q;
	cin >> n >> q;
	
	node st(0,1000000005);
	pii arr[n+1];
	for(int x=1;x<=n;x++){
		cin >>arr[x].first >> arr[x].second;
		st.upd(arr[x].second,{arr[x].first,x});
	}
	
	int two[25][n+5];
	memset(two,-1,sizeof(two));
	
	for(int x=1;x<=n;x++){
		pii hold=st.query(arr[x].first,arr[x].second);
		if(hold.first>=arr[x].first) continue;
		//show2(x,x,par,hold.second);
		two[0][x]=hold.second;
	}
	
	for(int x=0;x<20;x++){
		for(int y=1;y<=n;y++){
			if(two[x][y]==-1) continue;
			two[x+1][y]=two[x][two[x][y]];
		}
	}
	
	int l,r;
	for(int x=0;x<q;x++){
		cin >> l >> r;
		
		if(arr[r].second<arr[l].second){
			cout << "impossible\n";
			continue;
		}
		else if(l==r){
			cout << 0 << "\n";
			continue;
		}
		else if(arr[r].first<=arr[l].second&&arr[r].second>=arr[l].second){
			cout << 1 << "\n";
			continue;
		}
		
		int ans=0;
		for(int bit=19;bit>=0;bit--){
			if(two[bit][r]==-1) continue;
			int index=two[bit][r];
			if(arr[index].first>arr[l].second){
				ans+=1<<bit;
				r=index;
			}
		}
		//show(r,r);
		
		if(two[0][r]==-1||arr[two[0][r]].first>arr[l].second){
			cout << "impossible\n";
			continue;
		}
		
		cout << ans+2 << "\n";
	}
	
	
}	

int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

		

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	308 ms	182348 KB	Output is correct
3	Correct	318 ms	187728 KB	Output is correct
4	Correct	430 ms	191340 KB	Output is correct
5	Correct	335 ms	204556 KB	Output is correct
6	Correct	344 ms	214032 KB	Output is correct
7	Correct	327 ms	209124 KB	Output is correct
8	Correct	340 ms	280828 KB	Output is correct
9	Correct	371 ms	324436 KB	Output is correct
10	Correct	324 ms	179148 KB	Output is correct
11	Correct	347 ms	216264 KB	Output is correct
12	Correct	80 ms	46932 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	3 ms	2908 KB	Output is correct
4	Correct	3 ms	2908 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	1880 KB	Output is correct
7	Correct	4 ms	5208 KB	Output is correct
8	Correct	5 ms	5212 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	3 ms	2908 KB	Output is correct
4	Correct	3 ms	2908 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	1880 KB	Output is correct
7	Correct	4 ms	5208 KB	Output is correct
8	Correct	5 ms	5212 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	3 ms	3024 KB	Output is correct
13	Correct	3 ms	2908 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1696 KB	Output is correct
16	Correct	4 ms	5208 KB	Output is correct
17	Correct	4 ms	5228 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	28 ms	3632 KB	Output is correct
20	Correct	38 ms	13220 KB	Output is correct
21	Correct	29 ms	3672 KB	Output is correct
22	Correct	26 ms	8540 KB	Output is correct
23	Correct	43 ms	23376 KB	Output is correct
24	Correct	37 ms	23372 KB	Output is correct
25	Correct	38 ms	22964 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	3 ms	2908 KB	Output is correct
4	Correct	3 ms	2908 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	2 ms	1880 KB	Output is correct
7	Correct	4 ms	5208 KB	Output is correct
8	Correct	5 ms	5212 KB	Output is correct
9	Correct	1 ms	600 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	3 ms	2896 KB	Output is correct
13	Correct	3 ms	2904 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1884 KB	Output is correct
16	Correct	4 ms	5212 KB	Output is correct
17	Correct	4 ms	5212 KB	Output is correct
18	Correct	1 ms	604 KB	Output is correct
19	Correct	291 ms	182328 KB	Output is correct
20	Correct	84 ms	35156 KB	Output is correct
21	Correct	248 ms	103768 KB	Output is correct
22	Correct	279 ms	199404 KB	Output is correct
23	Correct	400 ms	322036 KB	Output is correct
24	Correct	402 ms	322212 KB	Output is correct
25	Correct	61 ms	22860 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	293 ms	182180 KB	Output is correct
2	Correct	326 ms	187896 KB	Output is correct
3	Correct	370 ms	191324 KB	Output is correct
4	Correct	398 ms	324276 KB	Output is correct
5	Correct	321 ms	179284 KB	Output is correct
6	Correct	434 ms	324220 KB	Output is correct
7	Correct	436 ms	323920 KB	Output is correct
8	Correct	446 ms	324304 KB	Output is correct
9	Correct	398 ms	322184 KB	Output is correct
10	Correct	463 ms	323880 KB	Output is correct
11	Correct	438 ms	323684 KB	Output is correct
12	Correct	426 ms	323556 KB	Output is correct

Subtask #6

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	308 ms	182348 KB	Output is correct
3	Correct	318 ms	187728 KB	Output is correct
4	Correct	430 ms	191340 KB	Output is correct
5	Correct	335 ms	204556 KB	Output is correct
6	Correct	344 ms	214032 KB	Output is correct
7	Correct	327 ms	209124 KB	Output is correct
8	Correct	340 ms	280828 KB	Output is correct
9	Correct	371 ms	324436 KB	Output is correct
10	Correct	324 ms	179148 KB	Output is correct
11	Correct	347 ms	216264 KB	Output is correct
12	Correct	80 ms	46932 KB	Output is correct
13	Correct	0 ms	344 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	3 ms	2908 KB	Output is correct
16	Correct	3 ms	2908 KB	Output is correct
17	Correct	1 ms	604 KB	Output is correct
18	Correct	2 ms	1880 KB	Output is correct
19	Correct	4 ms	5208 KB	Output is correct
20	Correct	5 ms	5212 KB	Output is correct
21	Correct	1 ms	600 KB	Output is correct
22	Correct	0 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	3 ms	3024 KB	Output is correct
25	Correct	3 ms	2908 KB	Output is correct
26	Correct	1 ms	604 KB	Output is correct
27	Correct	2 ms	1696 KB	Output is correct
28	Correct	4 ms	5208 KB	Output is correct
29	Correct	4 ms	5228 KB	Output is correct
30	Correct	1 ms	604 KB	Output is correct
31	Correct	28 ms	3632 KB	Output is correct
32	Correct	38 ms	13220 KB	Output is correct
33	Correct	29 ms	3672 KB	Output is correct
34	Correct	26 ms	8540 KB	Output is correct
35	Correct	43 ms	23376 KB	Output is correct
36	Correct	37 ms	23372 KB	Output is correct
37	Correct	38 ms	22964 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	0 ms	348 KB	Output is correct
40	Correct	3 ms	2896 KB	Output is correct
41	Correct	3 ms	2904 KB	Output is correct
42	Correct	1 ms	604 KB	Output is correct
43	Correct	2 ms	1884 KB	Output is correct
44	Correct	4 ms	5212 KB	Output is correct
45	Correct	4 ms	5212 KB	Output is correct
46	Correct	1 ms	604 KB	Output is correct
47	Correct	291 ms	182328 KB	Output is correct
48	Correct	84 ms	35156 KB	Output is correct
49	Correct	248 ms	103768 KB	Output is correct
50	Correct	279 ms	199404 KB	Output is correct
51	Correct	400 ms	322036 KB	Output is correct
52	Correct	402 ms	322212 KB	Output is correct
53	Correct	61 ms	22860 KB	Output is correct
54	Correct	293 ms	182180 KB	Output is correct
55	Correct	326 ms	187896 KB	Output is correct
56	Correct	370 ms	191324 KB	Output is correct
57	Correct	398 ms	324276 KB	Output is correct
58	Correct	321 ms	179284 KB	Output is correct
59	Correct	434 ms	324220 KB	Output is correct
60	Correct	436 ms	323920 KB	Output is correct
61	Correct	446 ms	324304 KB	Output is correct
62	Correct	398 ms	322184 KB	Output is correct
63	Correct	463 ms	323880 KB	Output is correct
64	Correct	438 ms	323684 KB	Output is correct
65	Correct	426 ms	323556 KB	Output is correct
66	Correct	0 ms	344 KB	Output is correct
67	Correct	295 ms	182352 KB	Output is correct
68	Correct	334 ms	187900 KB	Output is correct
69	Correct	348 ms	191212 KB	Output is correct
70	Correct	341 ms	204628 KB	Output is correct
71	Correct	346 ms	213988 KB	Output is correct
72	Correct	340 ms	209152 KB	Output is correct
73	Correct	339 ms	280960 KB	Output is correct
74	Correct	391 ms	324288 KB	Output is correct
75	Correct	336 ms	179236 KB	Output is correct
76	Correct	341 ms	215892 KB	Output is correct
77	Correct	78 ms	46924 KB	Output is correct
78	Correct	1 ms	348 KB	Output is correct
79	Correct	3 ms	2988 KB	Output is correct
80	Correct	3 ms	2908 KB	Output is correct
81	Correct	1 ms	604 KB	Output is correct
82	Correct	2 ms	1884 KB	Output is correct
83	Correct	5 ms	5212 KB	Output is correct
84	Correct	5 ms	5208 KB	Output is correct
85	Correct	1 ms	604 KB	Output is correct
86	Correct	27 ms	3824 KB	Output is correct
87	Correct	36 ms	13140 KB	Output is correct
88	Correct	29 ms	3664 KB	Output is correct
89	Correct	31 ms	8528 KB	Output is correct
90	Correct	42 ms	23632 KB	Output is correct
91	Correct	39 ms	23376 KB	Output is correct
92	Correct	39 ms	23384 KB	Output is correct
93	Correct	283 ms	182352 KB	Output is correct
94	Correct	83 ms	35132 KB	Output is correct
95	Correct	242 ms	103544 KB	Output is correct
96	Correct	281 ms	199504 KB	Output is correct
97	Correct	392 ms	322128 KB	Output is correct
98	Correct	415 ms	322164 KB	Output is correct
99	Correct	60 ms	22744 KB	Output is correct
100	Correct	437 ms	324156 KB	Output is correct
101	Correct	454 ms	324076 KB	Output is correct
102	Correct	435 ms	324816 KB	Output is correct
103	Correct	430 ms	323740 KB	Output is correct
104	Correct	445 ms	323640 KB	Output is correct
105	Correct	433 ms	323656 KB	Output is correct
106	Correct	128 ms	33876 KB	Output is correct
107	Correct	173 ms	37200 KB	Output is correct
108	Correct	279 ms	105616 KB	Output is correct
109	Correct	272 ms	105972 KB	Output is correct
110	Correct	453 ms	323920 KB	Output is correct
111	Correct	437 ms	324060 KB	Output is correct