답안 #589270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589270	2022-07-04T11:28:04 Z	codr0	Event Hopping (BOI22_events)	C++14	100 / 100	792 ms	19804 KB

events

// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>

#define bit(i,j) ((j>>i)&1)
#define minm(x,y) x=min(x,y)
#define maxm(x,y) x=max(x,y)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n'
#define wtf cout<<"WHAT THE FUCK!\n"
#define dmid int mid=(r+l)/2
#define lc 2*id
#define rc 2*id+1

using namespace std;
const int inf=1e9;
const int N=2e5+4;
const int SQ=2000;
const int lg=20;
int fen[N],S[N],E[N],ans[N],nxt[lg][N],rnk[N];
pii xy[N];
bool mark[N];
vector<int> vc;
int n,q;
int mnS;

	void upd(int k,int x){
		while(k<N){
			maxm(fen[k],x);
			k+=(k&(-k));
		}
	}

	int get(int k){
		int rt=0;
		while(k>0){
			maxm(rt,fen[k]);
			k-=(k&(-k));
		}
		return rt;
	}

	bool cmp(int i,int j){
		if(xy[i].S!=xy[j].S) return (xy[i].S<xy[j].S);
		return (xy[i].F<xy[j].F);
	}

	bool adj(int u,int v){
		return (E[u]>=S[v]&&E[u]<=E[v]);
	}

	void relax(){
		for(int v:vc) mark[v]=1;
		vc.clear();
		FOR(i,1,n) if(mark[i]){
			nxt[0][i]=get(E[i]);
			if(nxt[0][i]==i) nxt[0][i]=0;
		}
		FOR(j,1,lg-1) FOR(i,1,n-(1<<j)+1) nxt[j][i]=nxt[j-1][nxt[j-1][i]];
		mnS=inf;
	}

	void ADD(int v){
		if(SZ(vc)>=SQ) relax();
		for(int u:vc) if(adj(u,v)) nxt[0][u]=v;
		vc.pb(v);
		upd(S[v],v);
		minm(mnS,S[v]);
	}

	int go(int u,int v){
		if(adj(u,v)) return 0;
		int NXT=0;
		if(mark[u]) NXT=get(E[u]);
		else NXT=nxt[0][u];
		if(NXT==u) NXT=0;
		if(NXT==0) return inf;
		return (go(NXT,v)+1);
	}

	int dis(int u,int v){
		if(adj(u,v)) return 0;
		if(!mark[u]) return go(u,v);
		int rt=0;
		FORR(j,lg-1,0){
			if(nxt[j][u]!=0&&E[nxt[j][u]]<min(mnS,S[v])) rt+=(1<<j),u=nxt[j][u];
		}
		return min(inf,go(u,v)+rt);
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);	

	mnS=1e9;
	cin>>n>>q;
	FOR(i,1,n) cin>>xy[i].F>>xy[i].S;
	vector<pair<int,pii>> vz;
	FOR(i,1,n) vz.pb({xy[i].F,{i,0}}),vz.pb({xy[i].S,{i,1}});
	sort(all(vz));
	int bv=0;
	FOR(i,0,SZ(vz)-1){
		if(i==0||vz[i].F!=vz[i-1].F) bv++;
		if(vz[i].S.S==0) xy[vz[i].S.F].F=bv;
		else xy[vz[i].S.F].S=bv;
	}
	int RNK[n+1];
	FOR(i,1,n) RNK[i]=i;
	sort(RNK+1,RNK+n+1,cmp);
	FOR(i,1,n) rnk[RNK[i]]=i;
	FOR(i,1,n) E[rnk[i]]=xy[i].S;
	FOR(i,1,n) S[rnk[i]]=xy[i].F;
	vector<pair<pii,pii>> Q;
	FOR(i,1,q){
		int s,e; cin>>s>>e;
		Q.pb({{rnk[e],i},{rnk[s],rnk[e]}});
	}
	sort(all(Q));
	int last=1;
	FOR(i,0,q-1){
		while(last<=Q[i].S.S){
			ADD(last);
			last++;
		}	
		if(Q[i].S.F==Q[i].S.S){ ans[Q[i].F.S-1]=0; continue;}
		if(Q[i].S.F>Q[i].S.S){
			if(E[Q[i].S.F]==E[Q[i].S.S]) ans[Q[i].F.S-1]=1;
			else ans[Q[i].F.S-1]=inf;
			continue;
		}
		ans[Q[i].F.S-1]=dis(Q[i].S.F,Q[i].S.S)+1;
	}
	FOR(i,0,q-1){
		if(ans[i]>=inf) cout<<"impossible"; else cout<<ans[i];
		cout<<'\n';
	}


	return 0;
    }

Subtask #1

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	388 KB	Output is correct
2	Correct	772 ms	16352 KB	Output is correct
3	Correct	766 ms	16284 KB	Output is correct
4	Correct	507 ms	16260 KB	Output is correct
5	Correct	682 ms	16484 KB	Output is correct
6	Correct	652 ms	16516 KB	Output is correct
7	Correct	643 ms	16492 KB	Output is correct
8	Correct	250 ms	17288 KB	Output is correct
9	Correct	251 ms	17188 KB	Output is correct
10	Correct	351 ms	16668 KB	Output is correct
11	Correct	323 ms	16948 KB	Output is correct
12	Correct	119 ms	16308 KB	Output is correct

Subtask #2

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	3 ms	416 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct

Subtask #3

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	3 ms	416 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	2 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	1 ms	468 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	2 ms	468 KB	Output is correct
19	Correct	46 ms	3492 KB	Output is correct
20	Correct	253 ms	3420 KB	Output is correct
21	Correct	137 ms	3708 KB	Output is correct
22	Correct	40 ms	3836 KB	Output is correct
23	Correct	45 ms	3692 KB	Output is correct
24	Correct	46 ms	3560 KB	Output is correct
25	Correct	45 ms	3256 KB	Output is correct

Subtask #4

15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	2 ms	468 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 ms	468 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	3 ms	416 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	352 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	1 ms	468 KB	Output is correct
14	Correct	2 ms	468 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	2 ms	468 KB	Output is correct
17	Correct	2 ms	468 KB	Output is correct
18	Correct	2 ms	468 KB	Output is correct
19	Correct	240 ms	11896 KB	Output is correct
20	Correct	225 ms	11952 KB	Output is correct
21	Correct	283 ms	11984 KB	Output is correct
22	Correct	232 ms	12316 KB	Output is correct
23	Correct	336 ms	12356 KB	Output is correct
24	Correct	277 ms	13028 KB	Output is correct
25	Correct	349 ms	11680 KB	Output is correct

Subtask #5

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	785 ms	16388 KB	Output is correct
2	Correct	753 ms	16348 KB	Output is correct
3	Correct	527 ms	16300 KB	Output is correct
4	Correct	264 ms	17256 KB	Output is correct
5	Correct	332 ms	16644 KB	Output is correct
6	Correct	281 ms	16908 KB	Output is correct
7	Correct	300 ms	16884 KB	Output is correct
8	Correct	318 ms	17008 KB	Output is correct
9	Correct	427 ms	11792 KB	Output is correct
10	Correct	321 ms	16528 KB	Output is correct
11	Correct	438 ms	16152 KB	Output is correct
12	Correct	301 ms	16524 KB	Output is correct

Subtask #6

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	388 KB	Output is correct
2	Correct	772 ms	16352 KB	Output is correct
3	Correct	766 ms	16284 KB	Output is correct
4	Correct	507 ms	16260 KB	Output is correct
5	Correct	682 ms	16484 KB	Output is correct
6	Correct	652 ms	16516 KB	Output is correct
7	Correct	643 ms	16492 KB	Output is correct
8	Correct	250 ms	17288 KB	Output is correct
9	Correct	251 ms	17188 KB	Output is correct
10	Correct	351 ms	16668 KB	Output is correct
11	Correct	323 ms	16948 KB	Output is correct
12	Correct	119 ms	16308 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	2 ms	468 KB	Output is correct
16	Correct	1 ms	468 KB	Output is correct
17	Correct	1 ms	468 KB	Output is correct
18	Correct	2 ms	468 KB	Output is correct
19	Correct	2 ms	468 KB	Output is correct
20	Correct	3 ms	416 KB	Output is correct
21	Correct	2 ms	468 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	0 ms	340 KB	Output is correct
24	Correct	2 ms	468 KB	Output is correct
25	Correct	1 ms	468 KB	Output is correct
26	Correct	1 ms	468 KB	Output is correct
27	Correct	2 ms	468 KB	Output is correct
28	Correct	2 ms	468 KB	Output is correct
29	Correct	2 ms	468 KB	Output is correct
30	Correct	2 ms	468 KB	Output is correct
31	Correct	46 ms	3492 KB	Output is correct
32	Correct	253 ms	3420 KB	Output is correct
33	Correct	137 ms	3708 KB	Output is correct
34	Correct	40 ms	3836 KB	Output is correct
35	Correct	45 ms	3692 KB	Output is correct
36	Correct	46 ms	3560 KB	Output is correct
37	Correct	45 ms	3256 KB	Output is correct
38	Correct	0 ms	340 KB	Output is correct
39	Correct	0 ms	352 KB	Output is correct
40	Correct	1 ms	468 KB	Output is correct
41	Correct	1 ms	468 KB	Output is correct
42	Correct	2 ms	468 KB	Output is correct
43	Correct	2 ms	468 KB	Output is correct
44	Correct	2 ms	468 KB	Output is correct
45	Correct	2 ms	468 KB	Output is correct
46	Correct	2 ms	468 KB	Output is correct
47	Correct	240 ms	11896 KB	Output is correct
48	Correct	225 ms	11952 KB	Output is correct
49	Correct	283 ms	11984 KB	Output is correct
50	Correct	232 ms	12316 KB	Output is correct
51	Correct	336 ms	12356 KB	Output is correct
52	Correct	277 ms	13028 KB	Output is correct
53	Correct	349 ms	11680 KB	Output is correct
54	Correct	785 ms	16388 KB	Output is correct
55	Correct	753 ms	16348 KB	Output is correct
56	Correct	527 ms	16300 KB	Output is correct
57	Correct	264 ms	17256 KB	Output is correct
58	Correct	332 ms	16644 KB	Output is correct
59	Correct	281 ms	16908 KB	Output is correct
60	Correct	300 ms	16884 KB	Output is correct
61	Correct	318 ms	17008 KB	Output is correct
62	Correct	427 ms	11792 KB	Output is correct
63	Correct	321 ms	16528 KB	Output is correct
64	Correct	438 ms	16152 KB	Output is correct
65	Correct	301 ms	16524 KB	Output is correct
66	Correct	0 ms	340 KB	Output is correct
67	Correct	792 ms	16804 KB	Output is correct
68	Correct	774 ms	17400 KB	Output is correct
69	Correct	544 ms	16748 KB	Output is correct
70	Correct	688 ms	16992 KB	Output is correct
71	Correct	662 ms	16824 KB	Output is correct
72	Correct	669 ms	17412 KB	Output is correct
73	Correct	260 ms	17492 KB	Output is correct
74	Correct	268 ms	19804 KB	Output is correct
75	Correct	324 ms	17336 KB	Output is correct
76	Correct	339 ms	17092 KB	Output is correct
77	Correct	127 ms	16464 KB	Output is correct
78	Correct	0 ms	340 KB	Output is correct
79	Correct	2 ms	468 KB	Output is correct
80	Correct	2 ms	484 KB	Output is correct
81	Correct	2 ms	428 KB	Output is correct
82	Correct	2 ms	468 KB	Output is correct
83	Correct	2 ms	468 KB	Output is correct
84	Correct	2 ms	468 KB	Output is correct
85	Correct	2 ms	468 KB	Output is correct
86	Correct	46 ms	4124 KB	Output is correct
87	Correct	262 ms	4448 KB	Output is correct
88	Correct	143 ms	4132 KB	Output is correct
89	Correct	41 ms	4764 KB	Output is correct
90	Correct	49 ms	4632 KB	Output is correct
91	Correct	45 ms	4528 KB	Output is correct
92	Correct	54 ms	4164 KB	Output is correct
93	Correct	244 ms	13500 KB	Output is correct
94	Correct	217 ms	12736 KB	Output is correct
95	Correct	296 ms	13076 KB	Output is correct
96	Correct	233 ms	12220 KB	Output is correct
97	Correct	356 ms	12332 KB	Output is correct
98	Correct	282 ms	12760 KB	Output is correct
99	Correct	354 ms	11680 KB	Output is correct
100	Correct	282 ms	17268 KB	Output is correct
101	Correct	290 ms	17572 KB	Output is correct
102	Correct	322 ms	18608 KB	Output is correct
103	Correct	317 ms	18392 KB	Output is correct
104	Correct	474 ms	17576 KB	Output is correct
105	Correct	303 ms	18852 KB	Output is correct
106	Correct	381 ms	18488 KB	Output is correct
107	Correct	401 ms	18732 KB	Output is correct
108	Correct	334 ms	18620 KB	Output is correct
109	Correct	327 ms	17840 KB	Output is correct
110	Correct	453 ms	17464 KB	Output is correct
111	Correct	455 ms	17180 KB	Output is correct