oj.uz

Submission #589270

# Submission time Handle Problem Language Result Execution time Memory
589270 2022-07-04T11:28:04 Z codr0 Event Hopping (BOI22_events) C++14
100 / 100
 792 ms 19804 KB 
// 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

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

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

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

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

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

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