oj.uz

Submission #1000207

# Submission time Handle Problem Language Result Execution time Memory
1000207 2024-06-17T04:07:38 Z pcc Event Hopping (BOI22_events) C++17
0 / 100
 290 ms 10760 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1e5+10;

int ord[mxn],perm[mxn];
pii arr[mxn];

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	int seg[mxn];
	void modify(int now,int l,int r,int p,int v){
		if(l == r){
			seg[now] = v;
			return;
		}
		if(mid>=p)modify(ls,l,mid,p,v);
		else modify(rs,mid+1,r,p,v);
		seg[now] = min(seg[ls],seg[rs]);
	}
	int getval(int now,int l,int r,int s,int e){
		if(l>=s&&e>=r)return seg[now];
		if(mid>=e)return getval(ls,l,mid,s,e);
		else if(mid<s)return getval(rs,mid+1,r,s,e);
		else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
	}
#undef ls
#undef rs
#undef mid
};

SEG seg;
int dp[mxn][20];
int N,Q;

int get_range(int rp,int lim){
	int l = 1,r = rp;
	while(l != r){
		int mid = (l+r)>>1;
		int now = ord[mid];
		if(arr[now].sc<lim)l = mid+1;
		else r = mid;
	}
	return l;
}

void calc(int b){
	for(int i = 1;i<=N;i++)seg.modify(0,1,N,i,dp[i][b-1]);
	for(int i = N;i>=1;i--){
		dp[i][b] = seg.getval(0,1,N,dp[i][b-1],i);
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>Q;
	for(int i = 1;i<=N;i++)cin>>arr[i].fs>>arr[i].sc,ord[i] = i;
	sort(ord+1,ord+N+1,[](int a,int b){return arr[a].sc == arr[b].sc?arr[a].fs<arr[b].fs:arr[a].sc<arr[b].sc;});
	for(int i = 1;i<=N;i++)perm[ord[i]] = i;
	for(int i = N;i>=1;i--){
		int now = ord[i];
		int lp = get_range(i,arr[now].fs);
		dp[i][0] = lp;
	}
	for(int i = 1;i<20;i++)calc(i);
	while(Q--){
		int s,t;
		cin>>s>>t;
		if(s == t){
			cout<<"0\n";
			continue;
		}
		if(arr[s].sc == arr[t].sc){
			cout<<"1\n";
			continue;
		}
		s = perm[s],t = perm[t];
		if(s>t){
			cout<<"impossible\n";
			continue;
		}
		int ans = 0;
		for(int i = 19;i>=0;i--){
			if(dp[t][i]>s)t = dp[t][i],ans|=1<<i;
		}
		if(ans>N){
			cout<<"impossible\n";
		}
		else cout<<ans+1<<'\n';
	}

	/*
	for(int i = 1;i<=N;i++)cerr<<ord[i]<<' ';cout<<'\n';
	for(int i = 1;i<=N;i++){
		for(int j = 0;j<20;j++)cerr<<dp[i][j]<<' ';cout<<'\n';
	}
   */

	return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 290 ms 10760 KB Output is correct
3 Incorrect 262 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 10688 KB Output is correct
2 Incorrect 261 ms 10580 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 290 ms 10760 KB Output is correct
3 Incorrect 262 ms 10584 KB Output isn't correct
4 Halted 0 ms 0 KB -