oj.uz

Submission #589259

# Submission time Handle Problem Language Result Execution time Memory
589259 2022-07-04T11:06:39 Z codr0 Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 16232 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=1;
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 1576 ms 16228 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 0 ms 468 KB Output is correct
3 Correct 19 ms 596 KB Output is correct
4 Correct 20 ms 656 KB Output is correct
5 Correct 22 ms 596 KB Output is correct
6 Correct 19 ms 648 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 19 ms 648 KB Output is correct
9 Correct 15 ms 644 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 0 ms 468 KB Output is correct
3 Correct 19 ms 596 KB Output is correct
4 Correct 20 ms 656 KB Output is correct
5 Correct 22 ms 596 KB Output is correct
6 Correct 19 ms 648 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 19 ms 648 KB Output is correct
9 Correct 15 ms 644 KB Output is correct
10 Correct 0 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 20 ms 644 KB Output is correct
13 Correct 20 ms 648 KB Output is correct
14 Correct 19 ms 644 KB Output is correct
15 Correct 18 ms 596 KB Output is correct
16 Correct 19 ms 652 KB Output is correct
17 Correct 19 ms 652 KB Output is correct
18 Correct 14 ms 596 KB Output is correct
19 Correct 500 ms 3700 KB Output is correct
20 Correct 476 ms 3712 KB Output is correct
21 Correct 512 ms 4104 KB Output is correct
22 Correct 505 ms 3960 KB Output is correct
23 Correct 554 ms 3896 KB Output is correct
24 Correct 535 ms 3848 KB Output is correct
25 Correct 499 ms 3488 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 0 ms 468 KB Output is correct
3 Correct 19 ms 596 KB Output is correct
4 Correct 20 ms 656 KB Output is correct
5 Correct 22 ms 596 KB Output is correct
6 Correct 19 ms 648 KB Output is correct
7 Correct 20 ms 596 KB Output is correct
8 Correct 19 ms 648 KB Output is correct
9 Correct 15 ms 644 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 20 ms 640 KB Output is correct
13 Correct 19 ms 648 KB Output is correct
14 Correct 18 ms 596 KB Output is correct
15 Correct 19 ms 644 KB Output is correct
16 Correct 20 ms 648 KB Output is correct
17 Correct 19 ms 596 KB Output is correct
18 Correct 16 ms 632 KB Output is correct
19 Execution timed out 1585 ms 12732 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 1584 ms 16232 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 1576 ms 16228 KB Time limit exceeded
3 Halted 0 ms 0 KB -