oj.uz

Submission #702362

# Submission time Handle Problem Language Result Execution time Memory
702362 2023-02-23T16:47:19 Z andrei_iorgulescu Fountain (eJOI20_fountain) C++14
100 / 100
 269 ms 25024 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,q;
int d[100005],c[100005];
int dr[100005];
int sp[100005];
int nxt[100005][20];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> d[i] >> c[i];
    stack<int>st;
    for (int i = n; i >= 1; i--)
    {
        while (!st.empty() and d[st.top()] <= d[i])
            st.pop();
        if (!st.empty())
            dr[i] = st.top();
        else
            dr[i] = n + 1;
        st.push(i);
    }
    for (int i = n; i >= 1; i--)
        sp[i] = c[i] + sp[dr[i]];
    for (int i = 1; i <= n; i++)
        nxt[i][0] = dr[i];
    for (int j = 1; j <= 16; j++)
        for (int i = 1; i <= n; i++)
        {
            if (nxt[i][j - 1] == n + 1)
                nxt[i][j] = n + 1;
            else
                nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    for (int i = 1; i <= q; i++)
    {
        int r,v;
        cin >> r >> v;
        if (v > sp[r])
        {
            cout << "0\n";
            continue;
        }
        int pas = 16;
        while (pas != -1)
        {
            int wh = nxt[r][pas];
            //cout << r << ' ' << wh << '\n';
            if (wh != n + 1)
            {
                if (v > sp[r] - sp[wh])
                {
                    v -= (sp[r] - sp[wh]);
                    r = wh;
                }
            }
            pas--;
        }
        cout << r << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 22704 KB Output is correct
2 Correct 200 ms 21416 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 177 ms 22704 KB Output is correct
9 Correct 200 ms 21416 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 68 ms 13192 KB Output is correct
12 Correct 269 ms 25024 KB Output is correct
13 Correct 167 ms 24048 KB Output is correct
14 Correct 116 ms 23108 KB Output is correct
15 Correct 104 ms 23416 KB Output is correct