Submission #596913

#	Time	Username	Problem	Language	Result	Execution time	Memory
596913		Cookie	Fountain (eJOI20_fountain)	C++14	100 / 100	781 ms	34040 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];
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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40