Submission #1223295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223295		Aisha	Fountain (eJOI20_fountain)	C++20	0 / 100	563 ms	48836 KiB

fountain

#include "bits/stdc++.h"

using namespace std;

#define int long long

int inf = 1e18;

signed main() {
    int n, q;
    cin >> n >> q;

    vector <int> d(n + 1), c(n + 1); c[0] = 1e9;
    for (int i = 1; i <= n; i ++) cin >>  d[i] >> c[i]; 

    // Graph / Tree ni yaratish
    vector <vector <int>> g(n + 1);
    priority_queue <pair <int, int>> pq;

    for (int i = 1; i <= n; i ++) {
        while (!pq.empty() && -pq.top().first < d[i]) {
            g[i].push_back(pq.top().second);
            pq.pop();
        }
        pq.push({-d[i], i});
    }

    while (!pq.empty()) {
        g[0].push_back(pq.top().second);
        pq.pop();
    }


    // UP va SUM ni hisoblash
    int k = 21;
    vector <vector <int>> up(n + 1, vector <int> (k));
    vector <vector <int>> a(n + 1, vector <int> (k));
    
    auto dfs = [&](auto&& dfs, int i, int p) -> void {
        up[i][0] = p;
        a[i][0] = c[i] + c[p]; 
       // cout << i << ' ' << p << endl;
    
        for (int j = 1; j < k; j ++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            a[i][j] = a[i][j - 1] + a[up[i][j - 1]][j - 1]; 
        }

        for (int x : g[i]) {
            if (x != p) dfs(dfs, x, i);
        }
    }; 

    dfs(dfs, 0, 0);

    // SUM[P] >= V bo'lgan eng chuqur P ni topish (P I ning ajdodi)
    auto find = [&](int i, int v) -> int {
        if (c[i] >= v) return i;

        int x = i;
        for (int j = k - 1; j >= 0; j --) {
            // cout << x << endl;
            if (a[x][j] < v) x = up[x][j];
        }
        return up[x][0];
    };     


    while (q --) {
        int r, v;
        cin >> r >> v;
        cout << find(r, v) << endl;
    }

    return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40