oj.uz

Submission #596892

# Submission time Handle Problem Language Result Execution time Memory
596892 2022-07-15T08:49:01 Z Cookie Fountain (eJOI20_fountain) C++14
60 / 100
 74 ms 6288 KB 
#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] = {};
	    p[0] = 0;
	    for(int i = 2; i <= n; i++)assert(a[i] > a[i - 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 = mid; r = mid - 1;
	           }else{
	               l = mid + 1;
	           }
	       }
	       cout << ans << "\n";
	    }
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 3272 KB Output is correct
2 Correct 74 ms 6288 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 66 ms 3272 KB Output is correct
9 Correct 74 ms 6288 KB Output is correct
10 Runtime error 1 ms 620 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -