oj.uz

Submission #695067

# Submission time Handle Problem Language Result Execution time Memory
695067 2023-02-04T17:17:40 Z TheSahib Fountain (eJOI20_fountain) C++17
100 / 100
 809 ms 27048 KB 
#include <bits/stdc++.h>

#define ll long long
#define i128 __int128_t
#define pii pair<int, int>
#define oo 1e9 + 9

using namespace std;

int n;
vector<int> d;
vector<int> c;
vector<vector<int>> par;
vector<vector<ll>> st;
vector<int> msb;

void build(){
    msb.resize(n + 1, 0);
    for (int i = 2; i <= n; i++)
    {
        msb[i] = msb[i / 2] + 1;
    }
    st.resize(msb[n] + 1, vector<ll>(n + 1));
    par.resize(msb[n] + 1, vector<int>(n + 1));

    stack<int> s;
    s.push(n);
    for (int i = n; i >= 1; i--)
    {
        while(d[s.top()] <= d[i] && i != n){
            s.pop();
        }
        if(i == n){
            par[0][i] = n;
        }
        else{
            par[0][i] = s.top();
        }
        st[0][i] = c[i];
        s.push(i);
    }
    
    for (int j = 1; j <= msb[n]; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            par[j][i] = par[j - 1][par[j - 1][i]];
            st[j][i] = st[j - 1][i] + st[j - 1][par[j - 1][i]];
        }
    }
}

int ask(int r, ll v){
    int i = r;

    while(true){
        int j = 0;
        while(j <= msb[n] && v > st[j][i]){
            j++;
        }
        if(j == 0){
            break;
        }
        v -= st[j - 1][i];
        i = par[j - 1][i];
    }
    if(i == n) i = 0;
    return i;
}

int main()
{
    int q;
    cin >> n >> q;
    n++;
    d.resize(n + 1);
    c.resize(n + 1);

    for (int i = 1; i < n; i++)
    {
        cin >> d[i] >> c[i];
    }
    d[n] = oo;
    c[n] = oo;

    build();
    while(q--){
        ll r, v; cin >> r >> v;
        cout << ask(r, v) << '\n';
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 22976 KB Output is correct
2 Correct 565 ms 23072 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 5 ms 340 KB Output is correct
6 Correct 8 ms 468 KB Output is correct
7 Correct 5 ms 340 KB Output is correct
8 Correct 523 ms 22976 KB Output is correct
9 Correct 565 ms 23072 KB Output is correct
10 Correct 5 ms 468 KB Output is correct
11 Correct 267 ms 13960 KB Output is correct
12 Correct 809 ms 27048 KB Output is correct
13 Correct 730 ms 26664 KB Output is correct
14 Correct 502 ms 25900 KB Output is correct
15 Correct 436 ms 26252 KB Output is correct