Seletiva IOI 2014

robo.cpp

// Ivan Carvalho
// Robô - Seletiva IOI - OBI 2014
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = 1e9;
int X,Y,seg[4*MAXN],lazy[4*MAXN],L[MAXN],R[MAXN];
void propagate(int pos,int left,int right){
	if(lazy[pos] == 0) return;
	seg[pos] = lazy[pos];
	if(left != right){
		lazy[2*pos] = lazy[pos];
		lazy[2*pos+1] = lazy[pos];
	}
	lazy[pos] = 0;
	return;
}
void update(int pos,int left,int right,int i,int j,int val){
	propagate(pos,left,right);
	if(left>right||left>j||right<i) return;
	if(left >= i && right <= j){
		lazy[pos] = val;
		propagate(pos,left,right);
		return;
	}
	int mid = (left+right)/2;
	update(2*pos,left,mid,i,j,val);
	update(2*pos+1,mid+1,right,i,j,val);
	seg[pos] = min(seg[2*pos],seg[2*pos+1]);
}
int query(int pos,int left,int right,int i,int j){
	propagate(pos,left,right);
	if(left>right||left>j||right<i) return INF;
	if(left >= i && right <= j){
		return seg[pos];
	}
	int mid = (left+right)/2;
	int v1 = query(2*pos,left,mid,i,j);
	int v2 = query(2*pos+1,mid+1,right,i,j);
	return min(v1,v2);
}
int main(){
	scanf("%d %d",&Y,&X);
	Y++;
	X--;
	for(int i=1;i<=X;i++){
		scanf("%d %d",&L[i],&R[i]);
		L[i]++;
		R[i]++;
	}
	for(int i = X;i>=1;i--){
		int melhor = INF;
		if(L[i] != 1){
			melhor = min(melhor, query(1,1,Y,1,L[i]-1));
		}
		if(R[i] != Y){
			melhor = min(melhor, query(1,1,Y,R[i]+1,Y));
		}
		update(1,1,Y,L[i],R[i],melhor + 2);
	}
	printf("%d\n",query(1,1,Y,1,Y) + 1);
	return 0;
}