Problem: Example

Input

3 9
6 3
5 2
3 1
2
2
2


Output

2

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM -2000000000
#define SIZE 100000

struct Info{
	Info(ll arg_A,ll arg_B){
		A = arg_A;
		B = arg_B;
	}
	bool operator<(const struct Info& arg) const{ //A-Bの降順
		return A-B > arg.A-arg.B;
	}
	ll A,B;
};

int N;
ll* table;
ll* min_diff;
ll enemy[SIZE],self[SIZE],max_A[SIZE];
vector<Info> info;

//簡易化のため、要素数を2のべき乗にする関数
void init(int first_N){
	while(N < first_N)N *= 2;
}

void update(int loc,ll value){
	loc += N-1;

	table[loc] = value;

	if(N == 1)return;

	int parent = (loc-1)/2;

	while(true){
		table[parent] = max(table[2*parent+1],table[2*parent+2]); //親は左右の子の大きい方の値を持つ

		if(parent == 0)break;
		else{
			parent = (parent-1)/2;
		}
	}
}

void min_update(int loc,ll value){
	loc += N-1;

	min_diff[loc] = value;

	if(N == 1)return;

	int parent = (loc-1)/2;

	while(true){
		min_diff[parent] = min(min_diff[2*parent+1],min_diff[2*parent+2]); //親は左右の子の小さい方の値を持つ

		if(parent == 0)break;
		else{
			parent = (parent-1)/2;
		}
	}
}


ll query(int search_left,int search_right,int node_id,int node_left,int node_right){

	//今回のノードが検索区間をカバーしていなければ、結果に関係ない値を返す
	if(search_right < node_left || search_left > node_right)return NUM;

	//今回のノードの区間が、検索区間の部分区間である場合、今回のノードの値を返す
	if(search_left <= node_left && search_right >= node_right){
		return table[node_id];
	}

	//今回のノードの区間に、一部検索区間と重なっている区間がある場合→再帰的に子どもに尋ねる
	ll left_max= query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
	ll right_max = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

	return max(left_max,right_max);
}

ll min_query(int search_left,int search_right,int node_id,int node_left,int node_right){

	//今回のノードが検索区間をカバーしていなければ、結果に関係ない値を返す
	if(search_right < node_left || search_left > node_right)return BIG_NUM;

	//今回のノードの区間が、検索区間の部分区間である場合、今回のノードの値を返す
	if(search_left <= node_left && search_right >= node_right){
		return min_diff[node_id];
	}

	//今回のノードの区間に、一部検索区間と重なっている区間がある場合→再帰的に子どもに尋ねる
	ll left_min= min_query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
	ll right_min = min_query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);

	return min(left_min,right_min);
}

int main(){

	int first_N;
	ll L;

	scanf("%d %lld",&first_N,&L);

	ll A,B;
	for(int i = 0; i < first_N; i++){
		scanf("%lld %lld",&A,&B);
		info.push_back(Info(A,B));
	}

	//敵の高さを計算
	for(int i = 0; i < first_N; i++){
		scanf("%lld",&enemy[i]);
		if(i != 0){
			enemy[i] += enemy[i-1]; //累積和を計算
		}
	}

	sort(info.begin(),info.end());

	//自分の高さを計算
	for(int i = 0; i < first_N; i++){
		self[i] = info[i].A-info[i].B;
		if(i != 0){
			self[i] += self[i-1];
		}
	}
	//ある日を含め、ある日より右にある、最大のAを求める
	max_A[first_N-1] = info[first_N-1].A;
	for(int i = first_N-2; i >= 0; i--){
		max_A[i] = max(max_A[i+1],info[i].A);
	}

	//Bをセグメント木に登録する
	N = 1;
	init(first_N);

	table = new ll[2*N-1];

	//0～N-2が上位構造のアドレス、N-1～2*N-2が最小要素のアドレス
	for(int i = 0; i <= 2*N-2; i++)table[i] = NUM;  //まずは範囲外値で初期化
	//Bを登録
	for(int i = 0; i < first_N; i++){
		update(i,info[i].B);
	}

	//差をセグメント木に登録する
	min_diff = new ll[2*N-1];

	for(int i = 0; i <= 2*N-2; i++)min_diff[i] = BIG_NUM;
	//差を登録
	for(int i = 0; i < first_N; i++){
		if(i != 0){
			min_update(i,self[i]-enemy[i-1]);
		}else{
			min_update(i,self[i]);
		}
	}

	int ans = BIG_NUM;

	ll tmp_H;
	/*★A-Bの降順に値を採用、脱出日は最大のAを使用する場合★*/

	//初日で脱出可
	if(max_A[0] >= L){
		printf("1\n");
		return 0;
	}

	for(int i = 1; i < first_N; i++){

		if(self[i-1] <= enemy[i-1]){ //敵に追いつかれたので終了
			break;
		}
		tmp_H = self[i-1]+max_A[i];

		if(tmp_H >= L){
			ans = i+1; //解答は1オリジンのため
			break;
		}
	}

	bool FLG;

	/*★脱出日までの、どこか一日を、最終日に持ってくる場合★*/
	int left = 0,right,m;
	int min_index;
	ll max_B,tmp_diff;

	for(int i = 1; i < first_N; i++){

		if(self[i-1] <= enemy[i-1]){ //敵に追いつかれたので終了
			break;
		}
		//0～i日目の間で、i日目に順番を回しても、敵に追いつかれないドリンクの範囲を二分探索で求める
		right = i,m = (left+right)/2; //★始点は随時右にずれていくので、初期化せずに値を引き継ぐ

		min_index = BIG_NUM;

		while(left <= right){

			FLG = true;
			//ドリンクmを飲むのをi日目にすることで、敵に追いつかれるか調べる

			tmp_diff = min_query(m+1,i,0,0,N-1);

			if(tmp_diff <= info[m].A-info[m].B){
				FLG = false;
				break;
			}
			if(FLG){

				min_index = m;
				right = m-1;

			}else{
				left = m+1;
			}
			m = (left+right)/2;
		}

		if(min_index == BIG_NUM)continue;

		max_B = query(min_index,i,0,0,N-1); //★i日に回しても良いドリンクの中での、Bの最大値を取得★

		tmp_H = self[i]+max_B; //★★加算していたマイナスが消える分(マイナスのマイナス)、プラスになる

		if(tmp_H >= L){
			ans = min(ans,i+1);
			break;
		}
	}

	if(ans == BIG_NUM){
		printf("-1\n");
	}else{
		printf("%d\n",ans);
	}

	return 0;
}