oj.uz

Submission #1000208

# Submission time Handle Problem Language Result Execution time Memory
1000208 2024-06-17T04:13:31 Z pcc Event Hopping (BOI22_events) C++17
30 / 100
 275 ms 15556 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*4];
	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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 251 ms 11924 KB Output is correct
3 Correct 247 ms 11864 KB Output is correct
4 Correct 255 ms 14932 KB Output is correct
5 Correct 256 ms 15100 KB Output is correct
6 Correct 257 ms 15100 KB Output is correct
7 Correct 258 ms 15188 KB Output is correct
8 Correct 210 ms 15368 KB Output is correct
9 Correct 208 ms 15556 KB Output is correct
10 Correct 253 ms 15444 KB Output is correct
11 Correct 248 ms 15296 KB Output is correct
12 Correct 201 ms 14676 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 2396 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 4444 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 4444 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 2396 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 4444 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 4444 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 2 ms 2396 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 4444 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 11856 KB Output is correct
2 Correct 257 ms 11904 KB Output is correct
3 Correct 252 ms 15048 KB Output is correct
4 Correct 208 ms 15444 KB Output is correct
5 Correct 252 ms 15296 KB Output is correct
6 Correct 258 ms 15188 KB Output is correct
7 Correct 258 ms 15300 KB Output is correct
8 Correct 275 ms 15188 KB Output is correct
9 Correct 195 ms 13140 KB Output is correct
10 Correct 245 ms 14676 KB Output is correct
11 Correct 216 ms 14676 KB Output is correct
12 Correct 253 ms 14880 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 251 ms 11924 KB Output is correct
3 Correct 247 ms 11864 KB Output is correct
4 Correct 255 ms 14932 KB Output is correct
5 Correct 256 ms 15100 KB Output is correct
6 Correct 257 ms 15100 KB Output is correct
7 Correct 258 ms 15188 KB Output is correct
8 Correct 210 ms 15368 KB Output is correct
9 Correct 208 ms 15556 KB Output is correct
10 Correct 253 ms 15444 KB Output is correct
11 Correct 248 ms 15296 KB Output is correct
12 Correct 201 ms 14676 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 2 ms 2396 KB Output is correct
16 Correct 2 ms 2396 KB Output is correct
17 Correct 2 ms 2396 KB Output is correct
18 Incorrect 2 ms 4444 KB Output isn't correct
19 Halted 0 ms 0 KB -