Submission #1179981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179981		vladkonoval	Fountain (eJOI20_fountain)	C++20	60 / 100	1595 ms	3400 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
ll n,q,i,r[100007],v[100007],dp[100007],id,v1,res,cur,pip;
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for (i=1;i<=n;i++) {cin>>r[i]>>v[i];if (r[i]<=r[i-1]) pip = 10;}
    if (pip==10) {
        while (q--) {
            cin>>id>>v1;
            if (id>n) {cout<<0<<endl;continue;}
            res = v1;
            cur = id;
            res-=v[id];
            for (i=id+1;i<=n;i++) {
                if (res<=0) break;
                if (r[i]>r[cur]) {
                    res-=v[i];
                    cur = i;
                }
            }
            if (res>0) cout<<0<<endl;
            else
                cout<<cur<<endl;
        }
    }
    else {
        for (i=1;i<=n;i++) dp[i] = dp[i-1] + v[i];
        while (q--) {
            cin>>id>>v1;
            v1+=dp[id-1];
            auto it = lower_bound(dp+1,dp+1+n,v1)-dp;
            if (it>n) cout<<0<<endl;
            else
                cout<<it<<endl;
        }
    }

    return 0;
}

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