oj.uz

Submission #695057

# Submission time Handle Problem Language Result Execution time Memory
695057 2023-02-04T17:14:20 Z TheSahib Fountain (eJOI20_fountain) C++17
0 / 100
 95 ms 43412 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(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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Runtime error 2 ms 724 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 95 ms 43412 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Runtime error 2 ms 724 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -