oj.uz

Submission #467055

# Submission time Handle Problem Language Result Execution time Memory
467055 2021-08-21T13:33:48 Z Mamedov Fountain (eJOI20_fountain) C++17
100 / 100
 666 ms 17152 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define pis pair<int, string>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo 2000000002

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int up = 1e5 + 5;
const int lg = 18;
int D[up], C[up];
int sum[up][lg], par[up][lg];

void buildST(int n) {
    stack<int>st;
    D[0] = oo;
    st.push(0);
    for(int i = n; i >= 1; --i) {
        while(D[st.top()] <= D[i]) {
            st.pop();
        }
        par[i][0] = st.top();
        st.push(i);
    }
    for(int i = 0; i <= n; ++i) {
        sum[i][0] = C[i];
    }
    for(int j = 1; j < lg; ++j) {
        for(int i = 1; i <= n; ++i) {
            par[i][j] = par[par[i][j - 1]][j - 1];
            sum[i][j] = sum[i][j - 1] + sum[par[i][j - 1]][j - 1];
        }
    }
}

int query(int id, int vol) {
    for(int i = lg - 1; i >= 0 && id; --i) {
        if(sum[id][i] < vol) {
            vol -= sum[id][i];
            id = par[id][i];
        }
    }
    return id;
}
void solve() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> D[i] >> C[i];
    }
    buildST(n);
    int id, vol;
    while(q--) {
        cin >> id >> vol;
        cout << query(id, vol) << '\n';
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    solve();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 5 ms 460 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 15924 KB Output is correct
2 Correct 480 ms 15080 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 3 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 434 ms 15924 KB Output is correct
9 Correct 480 ms 15080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 260 ms 9884 KB Output is correct
12 Correct 666 ms 17048 KB Output is correct
13 Correct 564 ms 17152 KB Output is correct
14 Correct 527 ms 16956 KB Output is correct
15 Correct 466 ms 17036 KB Output is correct