oj.uz

Submission #827762

# Submission time Handle Problem Language Result Execution time Memory
827762 2023-08-16T17:47:27 Z TahirAliyev Fountain (eJOI20_fountain) C++17
0 / 100
 388 ms 35864 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, ll>

const int oo = 1e9 + 9;
const int MAX = 1e5 + 5, LOGMAX = 20;

int n, q;
int d[MAX], c[MAX];

pii par[LOGMAX][MAX];

int lift(int i, int l){
    int curl = l;
    int u = i;
    for (int j = LOGMAX - 1; j >= 0; j--)
    {
        if(curl - par[j][u].second > 0){
            curl -= par[j][u].second;
            u = par[j][u].first;
        }
    }
    return u;
}

int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i] >> c[i];
    }
    stack<pii> s;
    for (int i = 1; i <= n; i++)
    {
        while(!s.empty() && s.top().first < d[i]){
            int a = s.top().second;
            s.pop();
            par[0][a] = {i, c[a]}; 
            cout << a << " : " << i << '\n';
        }
        s.push({d[i], i});
    }
    while(!s.empty()){
        int a = s.top().second;
        s.pop();
        par[0][a] = {0, c[a]};
        cout << a << " : 0\n";
    }
    par[0][0] = {0, oo};

    for (int j = 1; j < LOGMAX; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            int m = par[j - 1][i].first;
            par[j][i].first = par[j - 1][m].first;
            par[j][i].second = par[j - 1][i].second + par[j - 1][m].second ;
        }
    }

    while(q--){
        int r, v; cin >> r >> v;
        cout << lift(r, v) << '\n';
    }
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 388 ms 35864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -