Submission #589270

#	Time	Username	Problem	Language	Result	Execution time	Memory
589270		codr0	Event Hopping (BOI22_events)	C++14	100 / 100	792 ms	19804 KiB

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30