oj.uz

Submission #589240

# Submission time Handle Problem Language Result Execution time Memory
589240 2022-07-04T10:53:36 Z codr0 Event Hopping (BOI22_events) C++14
30 / 100
 541 ms 21116 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) 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,1,n) ADD(i);
	relax();
	last=n+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 468 KB Output is correct
2 Correct 261 ms 18164 KB Output is correct
3 Correct 273 ms 18268 KB Output is correct
4 Correct 281 ms 18120 KB Output is correct
5 Correct 285 ms 18312 KB Output is correct
6 Correct 307 ms 18360 KB Output is correct
7 Correct 293 ms 18316 KB Output is correct
8 Correct 315 ms 19076 KB Output is correct
9 Correct 271 ms 19104 KB Output is correct
10 Correct 278 ms 18488 KB Output is correct
11 Correct 541 ms 18748 KB Output is correct
12 Correct 244 ms 18604 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 616 KB Output is correct
5 Incorrect 1 ms 596 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 18196 KB Output is correct
2 Correct 292 ms 18212 KB Output is correct
3 Correct 274 ms 18108 KB Output is correct
4 Correct 286 ms 19012 KB Output is correct
5 Correct 285 ms 18624 KB Output is correct
6 Correct 302 ms 18692 KB Output is correct
7 Correct 314 ms 19084 KB Output is correct
8 Correct 318 ms 21116 KB Output is correct
9 Correct 392 ms 14112 KB Output is correct
10 Correct 342 ms 19908 KB Output is correct
11 Correct 454 ms 19432 KB Output is correct
12 Correct 314 ms 19736 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 261 ms 18164 KB Output is correct
3 Correct 273 ms 18268 KB Output is correct
4 Correct 281 ms 18120 KB Output is correct
5 Correct 285 ms 18312 KB Output is correct
6 Correct 307 ms 18360 KB Output is correct
7 Correct 293 ms 18316 KB Output is correct
8 Correct 315 ms 19076 KB Output is correct
9 Correct 271 ms 19104 KB Output is correct
10 Correct 278 ms 18488 KB Output is correct
11 Correct 541 ms 18748 KB Output is correct
12 Correct 244 ms 18604 KB Output is correct
13 Correct 0 ms 468 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 616 KB Output is correct
17 Incorrect 1 ms 596 KB Output isn't correct
18 Halted 0 ms 0 KB -