oj.uz

Submission #435815

# Submission time Handle Problem Language Result Execution time Memory
435815 2021-06-23T18:30:07 Z stoyan_malinin Fountain (eJOI20_fountain) C++17
100 / 100
 151 ms 16296 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 10448 KB Output is correct
2 Correct 124 ms 13876 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 4 ms 4940 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5068 KB Output is correct
8 Correct 99 ms 10448 KB Output is correct
9 Correct 124 ms 13876 KB Output is correct
10 Correct 5 ms 5040 KB Output is correct
11 Correct 67 ms 9784 KB Output is correct
12 Correct 151 ms 16296 KB Output is correct
13 Correct 149 ms 14988 KB Output is correct
14 Correct 119 ms 14124 KB Output is correct
15 Correct 113 ms 14456 KB Output is correct