oj.uz

Submission #827763

# Submission time Handle Problem Language Result Execution time Memory
827763 2023-08-16T17:48:02 Z TahirAliyev Fountain (eJOI20_fountain) C++17
100 / 100
 586 ms 38380 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]}; 
        }
        s.push({d[i], i});
    }
    while(!s.empty()){
        int a = s.top().second;
        s.pop();
        par[0][a] = {0, c[a]};
    }
    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 572 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 804 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 31620 KB Output is correct
2 Correct 407 ms 32332 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 2 ms 572 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 4 ms 804 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 401 ms 31620 KB Output is correct
9 Correct 407 ms 32332 KB Output is correct
10 Correct 4 ms 704 KB Output is correct
11 Correct 214 ms 20440 KB Output is correct
12 Correct 586 ms 37476 KB Output is correct
13 Correct 467 ms 37252 KB Output is correct
14 Correct 446 ms 36472 KB Output is correct
15 Correct 403 ms 38380 KB Output is correct