Submission #596880

#	Time	Username	Problem	Language	Result	Execution time	Memory
596880		Cookie	Fountain (eJOI20_fountain)	C++14	30 / 100	72 ms	3500 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
const int mxn = 2e5 + 3;
int n, q;
ll a[100001], b[100001];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for(int i = 1; i <= n; i++)cin >> a[i] >> b[i];
	if(n <= 1000 && q <= 2000){
	    for(int i = 0; i < q; i++){
	        ll r, v; cin >> r >> v;
	        if(v <= b[r]){
	            cout << r << "\n";
	        }else{
	            ll curr = a[r];
	            v -= b[r];
	            for(int j = r + 1; j <= n; j++){
	                if(a[j] > curr){
	                    v -= b[j];
	                    if(v <= 0){
	                        cout << j << "\n";
	                        break;
	                    }
	                    curr = a[j];
	                }
	            }
	            if(v > 0)cout << 0 << "\n";
	        }
	    }
	}else{
	    ll p[n + 1] = {};
	    for(int  i = 1; i <= n; i++)p[i] = p[i - 1] + b[i];
	    for(int i = 0; i < q; i++){
	       ll rr, v; cin >> rr >> v;
	       int l = rr, r = n, ans = 0;
	       while(l <= r){
	           int mid = (l + r) >> 1;
	           if(p[mid] - p[rr - 1] >= v){
	               ans = l; r = mid - 1;
	           }else{
	               l = mid + 1;
	           }
	       }
	       cout << ans << "\n";
	    }
	}
}

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