oj.uz

Submission #596913

# Submission time Handle Problem Language Result Execution time Memory
596913 2022-07-15T09:16:39 Z Cookie Fountain (eJOI20_fountain) C++14
100 / 100
 781 ms 34040 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];
pair<ll, ll> up[100001][17];
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{
	    deque<int>dq;
	    dq.pb(n);;
	    for(int i = n - 1; i >= 1; i--){
	        while(dq.size() && a[dq.back()] <= a[i])dq.pop_back();
	        if(!dq.size())up[i][0].first = 0;
	        else{up[i][0].first = dq.back(); up[i][0].second = b[i];};
	        dq.pb(i);
	    }
	    
	    for(int i = 1; i < 17; i++){
	        for(int j = 1; j <= n; j++){
	            up[j][i].first = up[up[j][i - 1].first][i - 1].first;
	            up[j][i].second = up[j][i - 1].second + up[up[j][i - 1].first][i - 1].second;
	        }
	    }
	    for(int i = 0; i < q; i++){
	        ll rr, v; cin >> rr >> v;
	        if(v <= b[rr])cout << rr << "\n";
	        else{
	            int l = 0, r = n, ans = 0;
	            while(l <= r){
	                int mid = (l + r) >> 1;
	                ll cost = 0, id = rr;
	                for(int j = 0; j < 17; j++){
	                    if(mid & (1 << j)){
	                        
	                        cost += up[id][j].second;
	                        
	                        id = up[id][j].first;
	                    }
	                }
	                
	                if(id == 0){
	                    ans = 0; r = mid - 1;
	                }else{
	                    cost += b[id];
	                    if(cost >= v){
	                        ans = id; r = mid - 1;
	                    }else{
	                        l = mid + 1;
	                    }
	                }
	               
	            }
	            cout << ans << "\n";
	        }
	    }
	}
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 2 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 487 ms 28308 KB Output is correct
2 Correct 601 ms 26076 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 2 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 487 ms 28308 KB Output is correct
9 Correct 601 ms 26076 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 184 ms 18248 KB Output is correct
12 Correct 781 ms 34040 KB Output is correct
13 Correct 493 ms 33268 KB Output is correct
14 Correct 232 ms 32504 KB Output is correct
15 Correct 132 ms 32896 KB Output is correct