oj.uz

Submission #576084

# Submission time Handle Problem Language Result Execution time Memory
576084 2022-06-12T09:19:03 Z ddy888 Fountain (eJOI20_fountain) C++17
100 / 100
 1377 ms 30628 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 100010;

struct Fountain {
    int d, c;
} arr[MAXN];

int n, q;
int in[MAXN];
ll sum[MAXN];
vector<int> g[MAXN];

void dfs(int x, int p) {
    if (sum[x]) return;
    sum[x] += sum[p] + arr[x].c;
    for (auto i: g[x]) dfs(i, x);
}

struct Twok {
    vector<vector<int> > up;
    vector<int> dep;
    vector<int> dst;
    void init(int _n) {
        up.resize(_n + 1, vector<int>(20, -1));
        dep.resize(_n + 1);
    }
    void dfs(int x, int p, int d) {
        dep[x] = d;
        up[x][0] = p;
        for (int i = 1; i < 20; ++i) {
            if (up[x][i - 1] == -1) continue;
            up[x][i] = up[up[x][i - 1]][i - 1];
        }
        for (auto i: g[x]) {
            if (i == p) continue;
            dfs(i, x, d + 1);
        }
    }   
    int jump(int x, int k) {
        for (int i = 0; i < 20; ++i) {
            if (x == -1) return -1;
            if (k & (1 << i)) x = up[x][i];
        }
        return x;
    }
    int lca(int a, int b) {
        if (dep[a] < dep[b]) swap(a, b);
        a = jump(a, dep[a] - dep[b]); // same level
        if (a == b) return a;
        for (int i = 19; i >= 0; --i) {
            if (up[a][i] == -1 || up[b][i] == -1) continue;
            if (up[a][i] != up[b][i]) {
                a = up[a][i];
                b = up[b][i];
            }
        }
        return up[a][0];
    }
};

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> arr[i].d >> arr[i].c;

    stack<pi> st;
    for (int i = n; i >= 1; --i) {
        while (st.size() && st.top().fi <= arr[i].d) st.pop();
        if (st.size()) {
            g[st.top().si].pb(i);
            ++in[i];
        }
        st.push({arr[i].d, i});
    }   
    Twok twok; twok.init(n);
    for (int i = n; i >= 1; --i) {
        if (in[i] == 0) dfs(i, i), twok.dfs(i, -1, 0);
    }

    auto rsq = [&](int qs, int qe) {
        if (twok.jump(qe, 1) == -1) return sum[qs];
        return sum[qs] - sum[twok.jump(qe, 1)];
    };

    while (q--) {
        int r, u; cin >> u >> r;

        int lo = -1, hi = n + 1; // binary search kth parent
        while (lo + 1 < hi) {
            int mid = (lo + hi) >> 1;
            if (twok.jump(u, mid) == -1) {
                hi = mid;
                continue;
            }
            int v = twok.jump(u, mid);
            if (rsq(u, v) >= r) hi = mid;
            else lo = mid;
        }
        cout << max(0, twok.jump(u, hi)) << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 6 ms 2952 KB Output is correct
6 Correct 5 ms 2912 KB Output is correct
7 Correct 3 ms 2832 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1077 ms 28028 KB Output is correct
2 Correct 1096 ms 26424 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct
3 Correct 4 ms 2772 KB Output is correct
4 Correct 3 ms 2772 KB Output is correct
5 Correct 6 ms 2952 KB Output is correct
6 Correct 5 ms 2912 KB Output is correct
7 Correct 3 ms 2832 KB Output is correct
8 Correct 1077 ms 28028 KB Output is correct
9 Correct 1096 ms 26424 KB Output is correct
10 Correct 5 ms 2772 KB Output is correct
11 Correct 351 ms 14344 KB Output is correct
12 Correct 1377 ms 30628 KB Output is correct
13 Correct 771 ms 24564 KB Output is correct
14 Correct 350 ms 22784 KB Output is correct
15 Correct 192 ms 21544 KB Output is correct