Submission #894240

#	Time	Username	Problem	Language	Result	Execution time	Memory
894240		Minbaev	Fountain (eJOI20_fountain)	C++17	60 / 100	59 ms	6408 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
	int n,m,k;
	
	cin>>n>>m;
	int v[n][2]{};
	
	for(int i = 0;i<n;i++){
		cin>>v[i][0]>>v[i][1];
	}
	
	if(m<=2000){		
		while(m--){
			int a,b;
			cin>>a>>b;
			
			int last = -1, cnt = b;
			for(int i = a - 1;i<n;i++){
				if((last!=-1&&v[last][0]>=v[i][0]))continue;
				if(v[i][1]>=cnt){
					cout<<i+1<<"\n";
					cnt = 0;
					break;
				}
				else{
					cnt -= v[i][1];
					last = i;
				}
			}
			if(cnt>0)cout<<0<<"\n";
		}
		return;
	}
	else{
		vector<int>pref(n+1);
		
		for(int i = 1;i<=n;i++){
			pref[i] = pref[i-1];
			pref[i] += v[i-1][1];
		}
		
		while(m--){
			int a,b;
			cin>>a>>b;
			
			int dif = pref[a - 1];
			int l = a,r = n,ans = 0;
			while(l<=r){
				int mid = (l+r) / 2;
				if(pref[mid] - dif >= b){
					ans = mid ;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			cout<<ans<<"\n";
		}
		
	}
	
	
	
	
	
	
	
}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();

}
	

Compilation message (stderr)

fountain.cpp: In function 'void solve()':
fountain.cpp:6:10: warning: unused variable 'k' [-Wunused-variable]
    6 |  int n,m,k;
      |          ^

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