Submission #589223

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
589223	2022-07-04T10:45:18 Z	codr0	Event Hopping (BOI22_events)	C++14	20 / 100	782 ms	18948 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) 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(nxt[0][u]==0) 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	1 ms	340 KB	Output is correct
2	Correct	676 ms	18112 KB	Output is correct
3	Correct	650 ms	18112 KB	Output is correct
4	Correct	515 ms	18032 KB	Output is correct
5	Correct	617 ms	18184 KB	Output is correct
6	Correct	566 ms	18204 KB	Output is correct
7	Correct	594 ms	18272 KB	Output is correct
8	Correct	279 ms	18920 KB	Output is correct
9	Correct	267 ms	18948 KB	Output is correct
10	Correct	351 ms	18484 KB	Output is correct
11	Correct	324 ms	18572 KB	Output is correct
12	Correct	146 ms	17980 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	2 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	468 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	2 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	468 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	1 ms	468 KB	Output is correct
13	Correct	3 ms	420 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	3600 KB	Output is correct
20	Correct	225 ms	3728 KB	Output is correct
21	Correct	122 ms	3956 KB	Output is correct
22	Incorrect	41 ms	4044 KB	Output isn't correct
23	Halted	0 ms	0 KB	-

Subtask #4

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	2 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	468 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	258 ms	13596 KB	Output is correct
20	Correct	233 ms	13580 KB	Output is correct
21	Incorrect	312 ms	13560 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	694 ms	18024 KB	Output is correct
2	Correct	782 ms	17996 KB	Output is correct
3	Correct	501 ms	17996 KB	Output is correct
4	Correct	298 ms	18836 KB	Output is correct
5	Correct	344 ms	18328 KB	Output is correct
6	Incorrect	333 ms	18508 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #6

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	676 ms	18112 KB	Output is correct
3	Correct	650 ms	18112 KB	Output is correct
4	Correct	515 ms	18032 KB	Output is correct
5	Correct	617 ms	18184 KB	Output is correct
6	Correct	566 ms	18204 KB	Output is correct
7	Correct	594 ms	18272 KB	Output is correct
8	Correct	279 ms	18920 KB	Output is correct
9	Correct	267 ms	18948 KB	Output is correct
10	Correct	351 ms	18484 KB	Output is correct
11	Correct	324 ms	18572 KB	Output is correct
12	Correct	146 ms	17980 KB	Output is correct
13	Correct	1 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	2 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	468 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	1 ms	468 KB	Output is correct
25	Correct	3 ms	420 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	3600 KB	Output is correct
32	Correct	225 ms	3728 KB	Output is correct
33	Correct	122 ms	3956 KB	Output is correct
34	Incorrect	41 ms	4044 KB	Output isn't correct
35	Halted	0 ms	0 KB	-