oj.uz

Submission #1000209

# Submission time Handle Problem Language Result Execution time Memory
1000209 2024-06-17T04:30:56 Z pcc Event Hopping (BOI22_events) C++17
20 / 100
 273 ms 15520 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 15028 KB Output is correct
2 Correct 249 ms 14932 KB Output is correct
3 Correct 254 ms 15040 KB Output is correct
4 Correct 214 ms 15520 KB Output is correct
5 Correct 247 ms 15392 KB Output is correct
6 Correct 261 ms 15192 KB Output is correct
7 Correct 258 ms 15172 KB Output is correct
8 Correct 273 ms 15360 KB Output is correct
9 Correct 203 ms 13148 KB Output is correct
10 Correct 245 ms 14672 KB Output is correct
11 Correct 225 ms 14532 KB Output is correct
12 Correct 243 ms 14676 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4456 KB Output isn't correct
2 Halted 0 ms 0 KB -