Submission #576084

#	Time	Username	Problem	Language	Result	Execution time	Memory
576084		ddy888	Fountain (eJOI20_fountain)	C++17	100 / 100	1377 ms	30628 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40