oj.uz

Submission #641443

# Submission time Handle Problem Language Result Execution time Memory
641443 2022-09-16T18:19:27 Z Valaki2 Fountain (eJOI20_fountain) C++14
100 / 100
 255 ms 22784 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back

const int inf = 1e9 + 42;
const int maxn = 1e5;
const int maxlogn = 20;

int n, q;
int diam[1 + maxn];
int cap[1 + maxn];
int par[1 + maxn];
int bl_pos[1 + maxn][maxlogn];
int bl_amount[1 + maxn][maxlogn];

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> diam[i] >> cap[i];
    }
    diam[0] = inf;
    par[0] = 0;
    stack<int> s;
    s.push(0);
    for(int i = n; i >= 1; i--) {
        while(diam[s.top()] <= diam[i]) {
            s.pop();
        }
        par[i] = s.top();
        s.push(i);
    }
    for(int i = 0; i <= n; i++) {
        bl_pos[i][0] = par[i];
        bl_amount[i][0] = cap[i];
    }
    for(int j = 1; j < maxlogn; j++) {
        for(int i = 0; i <= n; i++) {
            bl_pos[i][j] = bl_pos[bl_pos[i][j - 1]][j - 1];
            bl_amount[i][j] = bl_amount[i][j - 1] + bl_amount[bl_pos[i][j - 1]][j - 1];
        }
    }
    for(int qi = 1; qi <= q; qi++) {
        int pos, val;
        cin >> pos >> val;
        for(int i = maxlogn - 1; i >= 0; i--) {
            if(val > bl_amount[pos][i]) {
                val -= bl_amount[pos][i];
                pos = bl_pos[pos][i];
            }
        }
        cout << pos << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    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 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 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 20316 KB Output is correct
2 Correct 185 ms 19340 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 464 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 177 ms 20316 KB Output is correct
9 Correct 185 ms 19340 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 77 ms 11872 KB Output is correct
12 Correct 255 ms 22784 KB Output is correct
13 Correct 161 ms 22064 KB Output is correct
14 Correct 157 ms 21180 KB Output is correct
15 Correct 115 ms 21444 KB Output is correct