Submission #775995

#	Time	Username	Problem	Language	Result	Execution time	Memory
775995		vjudge1	Fountain (eJOI20_fountain)	C++17	60 / 100	64 ms	6188 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl "\n"
#define ll long long
#define pb push_back
#define N 2000005                                                                                
int main(){
	lalala;
	int n,q;cin>>n>>q;
	ll int arr[n][2],pre[n+2];
	pre[0]=0;
	pre[n+1]=1000000000000000000;
	for(int i=0;i<n;i++){
		cin>>arr[i][0]>>arr[i][1];
		pre[i+1]=arr[i][1]+pre[i];
	}
	if(q<=2000&&n<=1000){
		while(q--){
			ll int x,y;cin>>x>>y;
			x--;
			ll int cev=-1,cur=arr[x][0]-1;
			for(int i=x;i<n;i++){
				if(arr[i][0]<=cur)continue;
				cur=arr[i][0];
				//cout<<y<<" "<<arr[i][1]<<" "<<i<<endl;
				if(arr[i][1]<y){
					y-=arr[i][1];continue;
				}
				cev=i;
				break;
			}
			cout<<cev+1<<endl;
		}return 0;
	}

	while(q--){
		ll int x,y;cin>>x>>y;
		ll int eksi=pre[x-1];
		int l=x,r=n+1;
		while(l<r){
			int m=(l+r)/2;
			ll int deg=pre[m]-eksi;
			if(deg>=y){
				r=m;
			}
			else l=m+1;
		}
		if(l==n+1)l=0;
		cout<<l<<endl;
	}


}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40