Submission #760789

#	Time	Username	Problem	Language	Result	Execution time	Memory
760789		bachhoangxuan	Fountain (eJOI20_fountain)	C++17	100 / 100	301 ms	10264 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define maxn 100005
const int inf=1e18;
const int bl=320;
int n,q,a[maxn],x[maxn],nxt[maxn],sum[maxn],sxt[maxn];
signed 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] >> x[i];
    a[n+1]=x[n+1]=inf;
    vector<int> Max;Max.push_back(n+1);
    for(int i=n;i>=1;i--){
        while(a[i]>=a[Max.back()]) Max.pop_back();
        nxt[i]=Max.back();Max.push_back(i);
    }
    for(int i=1;i<=n;i++){
        int u=i;
        for(int j=0;j<bl;j++){
            sum[i]+=x[u];
            if(u==n+1) break;
            else u=nxt[u];
        }
        sxt[i]=u;
    }
    for(int i=1;i<=q;i++){
        int r,v;cin >> r >> v;
        while(true){
            if(r==n+1) break;
            if(sum[r]<v){
                v-=sum[r];
                r=sxt[r];
            }
            else if(x[r]<v){
                v-=x[r];r=nxt[r];
            }
            else break;
        }
        if(r!=n+1) cout << r << '\n';
        else cout << 0 << '\n';
    }
}

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