Submission #908198

#	Time	Username	Problem	Language	Result	Execution time	Memory
908198		zyq181	Fountain (eJOI20_fountain)	C++17	100 / 100	200 ms	19360 KiB

fountain

#include <bits/stdc++.h>
#include <fstream>
using namespace std;
#define int long long 
const int MOD = 998244353;

//stack: value, suff

int N,Q;
int inp1, inp2;
vector<pair<int, int> > v; //reversed original {d, c}
vector<pair<int, pair<int, int> > > s; //{d, {suff, idx} }
vector<pair<int, pair<int, int> > > q; //sorted in decreasing index {idx, {wtr, qid} }

int ans[200010];

int32_t main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    cin >> N >> Q;
    for(int a=0; a<N; a++){
        cin >> inp1 >> inp2;
        v.push_back({inp1, inp2});
    }
    reverse(v.begin(), v.end());
    for(int a=0; a<Q; a++){
        cin >> inp1 >> inp2;
        q.push_back({inp1, {inp2, a}});
    }
    sort(q.begin(), q.end());
    for(int a=0; a<N; a++){
        //cout << "OK";
        int d, c;
        tie(d, c) = v[a];
        while(!s.empty() && s.back().first <= d){
            s.pop_back();
        }
        if(s.empty()){
            s.push_back({d, {c, N - a}});
        }
        else{
            int k = s.back().second.first;
            s.push_back({d, {c + k, N - a}});
        }
        /*
        cout << "AT " << N - a << " the stack is: \n";
        for(auto it: s){
            cout << it.first << ' ' << it.second.first << ' ' << it.second.second << '\n';
        } 
        cout << "\n\n";
        */
        while(!q.empty() && q.back().first == (N - a)){
            int qv = q.back().second.first;
            int id = q.back().second.second;
            q.pop_back();
            if(s.back().second.first < qv) ans[id] = 0;
            else{
                int lo = 0;
                int hi = s.size() - 1;
                int tot = s.back().second.first;
                while(lo < hi){
                    int mid = (lo + hi)/2;
                    if(tot - s[mid].second.first >= qv){
                        lo = mid + 1;
                    }
                    else{
                        hi = mid;
                    }
                }
                ans[id] = s[lo].second.second;
            }
        }
    }
    for(int a=0; a<Q; a++){
        cout << ans[a] << '\n';
    }
}

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