Call a Cab

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

ll dm[222];
ll hr[222];

ll d[101010];
ll h[101010];

const int mlg=19;

ll miq[100101][19];
ll maq[101010][19];
int lg[101010];

const ll inf=1e18;

ll getmin(int a, int b){
	int le=b-a+1;
	return min(miq[a][lg[le]], miq[b-(1<<lg[le])+1][lg[le]]);
}

ll getmax(int a, int b){
	int le=b-a+1;
	return max(maq[a][lg[le]], maq[b-(1<<lg[le])+1][lg[le]]);
}

const int N=1<<17;
int st[2*N];
void setmin(int a, int b, int v){
	a+=N;
	b+=N;
	while (a<=b){
		if (a%2){
			st[a]=min(st[a], v);
			a++;
		}
		if (!(b%2)){
			st[b]=min(st[b], v);
			b--;
		}
		a/=2;
		b/=2;
	}
}

const int inf2=1e9;

int getmin2(int i){
	int mi=inf2;
	for (i+=N;i;i/=2){
		mi=min(mi, st[i]);
	}
	return mi;
}

int dp[2*N];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t,n;
	cin>>t>>n;
	for (int i=0;i<t;i++){
		cin>>dm[i]>>hr[i];
	}
	for (int i=1;i<n;i++){
		cin>>d[i]>>h[i];
		d[i]+=d[i-1];
		h[i]+=h[i-1];
		//cout<<h[i]<<endl;
	}
	for (int i=1;i<=n+10;i++){
		while ((1<<lg[i])*2<i) lg[i]++;
	}
	for (int k=0;k<mlg;k++){
		for (int i=0;i<n;i++){
			if (k==0){
				miq[i][k]=h[i];
				maq[i][k]=h[i];
			}
			else{
				miq[i][k]=miq[i][k-1];
				maq[i][k]=maq[i][k-1];
				if (i+(1<<(k-1))<n){
					miq[i][k]=min(miq[i][k], miq[i+(1<<(k-1))][k-1]);
					maq[i][k]=max(maq[i][k], maq[i+(1<<(k-1))][k-1]);
				}
			}
		}
	}
	for (int i=0;i<2*N;i++){
		st[i]=inf2;
	}
	setmin(0, 0, 0);
	for (int i=0;i<n-1;i++){
		dp[i]=getmin2(i);
		//cout<<i<<" "<<dp[i]<<endl;
		for (int j=0;j<t;j++){
			int mi=i+1;
			int ma=n-1;
			int v=n+1;
			while (mi<=ma){
				int mid=(mi+ma)/2;
				if (d[mid]-d[i]>=dm[j]){
					v=min(v, mid);
					ma=mid-1;
				}
				else{
					mi=mid+1;
				}
			}
			//cout<<j<<" v "<<v<<" "<<d[2]-d[1]<<" "<<dm[j]<<endl;
			if (v>n-1) continue;
			mi=v;
			ma=n-1;
			int v2=0;
			while (mi<=ma){
				int mid=(mi+ma)/2;
				ll mah=getmax(i+1, mid);
				ll mih=getmin(i+1, mid);
				if (mah-mih<hr[j]||mid==i+1){
					v2=max(v2, mid);
					mi=mid+1;
				}
				else{
					ma=mid-1;
				}
			}
			//cout<<j<<" "<<v<<" "<<v2<<endl;
			if (v2>i&&v<=v2){
				setmin(v, v2, dp[i]+1);
			}
		}
	}
	dp[n-1]=getmin2(n-1);
	if (dp[n-1]<inf2){
		cout<<dp[n-1]<<endl;
	}
	else{
		cout<<"IMPOSSIBLE"<<endl;
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED