Submission #577855

#	Time	Username	Problem	Language	Result	Execution time	Memory
577855		vanic	Event Hopping (BOI22_events)	C++14	100 / 100	369 ms	19612 KiB

events

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int maxn=1e5+5, Log=17, pot=(1<<Log), inf=1e9;
 
struct tournament{
	int t[pot*2];
	tournament(){
		for(int i=1; i<pot*2; i++){
			t[i]=inf;
		}
	}
	void update(int x, int val){
		t[x]=min(t[x], val);
		for(x/=2; x>0; x/=2){
			t[x]=min(t[x*2], t[x*2+1]);
		}
	}
	int query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		int lijeva=inf, desna=inf;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return min(lijeva, desna);
	}
	int nadji(int L, int D, int x, int l, int d, int val){
		if(L>=l && D<=d){
			if(t[x]==val){
				while(x<pot){
					if(t[x*2]==val){
						x*=2;
					}
					else{
						x=x*2+1;
					}
				}
				return x;
			}
			return -1;
		}
		int xx=-1;
		if((L+D)/2>=l){
			xx=nadji(L, (L+D)/2, x*2, l, d, val);
			if(xx!=-1){
				return xx;
			}
		}
		if((L+D)/2+1<=d){
			xx=nadji((L+D)/2+1, D, x*2+1, l, d, val);
			if(xx!=-1){
				return xx;
			}
		}
		return -1;
	}
};

tournament T;

 
pair < int, int > a[maxn];
set < int > s;
map < int, int > m;

int digni[maxn][Log];
int moj[maxn];

void precompute(){
	for(int i=1; i<Log; i++){
		for(int j=0; j<maxn; j++){
			digni[j][i]=j;
		}
	}
	for(int i=1; i<Log; i++){
		for(int j=0; j<maxn; j++){
			digni[j][i]=digni[digni[j][i-1]][i-1];
		}
	}
}

int provjeri(int x, int y){
	if(x==y){
		return 0;
	}
	if(a[y].first<=a[x].second && a[x].second<=a[y].second){
		return 1;
	}
	if(a[x].second>a[y].second){
		return -1;
	}
	int uk=1;
	x=a[x].second;
	y=moj[y];
	if(T.t[y+pot]<=x){
		return 2;
	}
//	cout << "aha " << x << ' ' <<  y << endl;
//	cout << T.t[digni[y][0]+pot] << endl;
	for(int i=Log-1; i>-1; i--){
		if(T.t[digni[y][i]+pot]>x){
//			cout << "dizem " << y << " na " << digni[y][i] << endl;
			y=digni[y][i];
			uk+=(1<<i);
		}
	}
	
	if(uk>maxn){
		return -1;
	}
	return uk+2;
}
 
int main(){
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i=1; i<=n; i++){
		scanf("%d%d", &a[i].first, &a[i].second);
		s.insert(a[i].second);
	}
	int br=0;
	
	for(auto it=s.begin(); it!=s.end(); it++){
		m[*it]=br;
		br++;
	}
	set < int >::iterator it;
	for(int i=1; i<=n; i++){
		it=s.lower_bound(a[i].first);
		a[i]={m[*it], m[a[i].second]};
//		cout << a[i].first << ' ' << a[i].second << endl;
		T.update(a[i].second+pot, a[i].first);
	}
	int val, pos;
	for(int i=1; i<=n; i++){
		val=T.query(0, pot-1, 1, a[i].first, a[i].second);
//		cout << "vrijednost " << a[i].second << " je " << val << endl;
		if(val==a[i].first){
			moj[i]=a[i].second;
			continue;
		}
		pos=T.nadji(0, pot-1, 1, a[i].first, a[i].second, val);
		moj[i]=pos-pot;
	}
	int gran;
	for(int i=0; i<br; i++){
		gran=T.t[i+pot];
		val=T.query(0, pot-1, 1, gran, i);
		if(val==gran){
			digni[i][0]=i;
			continue;
		}
		pos=T.nadji(0, pot-1, 1, gran, i, val);
		digni[i][0]=pos-pot;
	}
	precompute();
/*	cout << "ovo sranje" << endl;
	for(int i=1; i<=n; i++){
		cout << moj[i] << ' ';
	}
	cout << endl;
	for(int i=0; i<br; i++){
		cout << T.t[i+pot] << ' ';
	}
	cout << endl;
	for(int i=0; i<br; i++){
		cout << digni[i][0] << ' ';
	}
	cout << endl;
	for(int i=0; i<br; i++){
		for(int j=0; j<3; j++){
			cout << digni[i][j] << ' ';
		}
		cout << endl;
	}*/
	int x, y, z;
	for(int i=0; i<q; i++){
		scanf("%d%d", &x, &y);
		z=provjeri(x, y);
		if(z==-1){
			printf("impossible\n");
		}
		else{
			printf("%d\n", z);
		}
	}
	return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:129:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
events.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |   scanf("%d%d", &a[i].first, &a[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp:191:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30