제출 #1000207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1000207		pcc	Event Hopping (BOI22_events)	C++17	0 / 100	290 ms	10760 KiB

events

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30