Submission #435815

#	Time	Username	Problem	Language	Result	Execution time	Memory
435815		stoyan_malinin	Fountain (eJOI20_fountain)	C++17	100 / 100	151 ms	16296 KiB

fountain

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2e5 + 5;

struct SmartStack
{
    vector <pair <int, int>> v;
    vector <int> prefSum;

    int getSum(int ind)
    {
        if(ind==0) return prefSum.back();
        return prefSum.back() - prefSum[ind-1];
    }

    void push(pair <int, int> x)
    {
        v.push_back(x);

        if(prefSum.empty()==true) prefSum.push_back(x.second);
        else
        {
            int sum = prefSum.back() + x.second;
            prefSum.push_back(sum);
        }
    }

    void pop()
    {
        v.pop_back();
        prefSum.pop_back();
    }

    pair <int, int> top()
    {
        return v.back();
    }

    bool isEmpty()
    {
        return v.empty();
    }
};

struct Query
{
    int qInd, v;

    Query(){}
    Query(int qInd, int v)
    {
        this->qInd = qInd;
        this->v = v;
    }
};

int findLastReservoir(SmartStack &st, int v)
{
    int l = 0, r = st.v.size()-1, mid;

    while(l+1<r)
    {
        mid = (l+r)/2;

        if(st.getSum(mid)>=v) l = mid;
        else r = mid - 1;
    }

    if(st.getSum(r)>=v) return st.v[r].first + 1;
    if(st.getSum(l)>=v) return st.v[l].first + 1;
    return 0;
}

int n;
int d[MAXN], c[MAXN];
vector <Query> queries[MAXN];

int ans[MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int Q;
    cin >> n >> Q;
    for(int i = 0;i<n;i++) cin >> d[i] >> c[i];

    for(int q = 0;q<Q;q++)
    {
        int r, v;
        cin >> r >> v;

        r--;
        queries[r].emplace_back(q, v);
    }

    SmartStack st;
    for(int i = n-1;i>=0;i--)
    {
        while(st.isEmpty()==false && d[st.top().first]<=d[i]) st.pop();
        st.push({i, c[i]});

        for(Query &q: queries[i])
        {
            ans[q.qInd] = findLastReservoir(st, q.v);
        }
    }

    for(int q = 0;q<Q;q++) cout << ans[q] << '\n';
}
/*
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

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