oj.uz

Submission #589256

# Submission time Handle Problem Language Result Execution time Memory
589256 2022-07-04T11:04:53 Z codr0 Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 16312 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=0;
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Execution timed out 1588 ms 16312 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 18 ms 652 KB Output is correct
5 Correct 18 ms 648 KB Output is correct
6 Correct 19 ms 596 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 18 ms 772 KB Output is correct
9 Correct 15 ms 596 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 18 ms 652 KB Output is correct
5 Correct 18 ms 648 KB Output is correct
6 Correct 19 ms 596 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 18 ms 772 KB Output is correct
9 Correct 15 ms 596 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 18 ms 596 KB Output is correct
13 Correct 18 ms 660 KB Output is correct
14 Correct 18 ms 596 KB Output is correct
15 Correct 19 ms 656 KB Output is correct
16 Correct 19 ms 648 KB Output is correct
17 Correct 19 ms 664 KB Output is correct
18 Correct 13 ms 648 KB Output is correct
19 Correct 489 ms 3960 KB Output is correct
20 Correct 472 ms 3744 KB Output is correct
21 Correct 474 ms 4116 KB Output is correct
22 Correct 495 ms 4096 KB Output is correct
23 Correct 527 ms 4652 KB Output is correct
24 Correct 502 ms 4584 KB Output is correct
25 Correct 475 ms 4204 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 18 ms 596 KB Output is correct
4 Correct 18 ms 652 KB Output is correct
5 Correct 18 ms 648 KB Output is correct
6 Correct 19 ms 596 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 18 ms 772 KB Output is correct
9 Correct 15 ms 596 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 0 ms 468 KB Output is correct
12 Correct 18 ms 644 KB Output is correct
13 Correct 19 ms 596 KB Output is correct
14 Correct 19 ms 556 KB Output is correct
15 Correct 19 ms 656 KB Output is correct
16 Correct 20 ms 636 KB Output is correct
17 Correct 19 ms 656 KB Output is correct
18 Correct 13 ms 596 KB Output is correct
19 Execution timed out 1562 ms 12860 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1571 ms 16224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Execution timed out 1588 ms 16312 KB Time limit exceeded
3 Halted 0 ms 0 KB -