Submission #1223314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223314		Aisha	Fountain (eJOI20_fountain)	C++20	0 / 100	303 ms	49584 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 {
        if (i) up[i][0] = p;
        if (i) a[i][0] = c[i] + c[p];
    
        for (int j = 1; j < k; j ++) {
            if (i) up[i][j] = up[up[i][j - 1]][j - 1];
            if (i) 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; int sum = c[i];
        for (int j = k - 1; j >= 0; j --) {
            if (a[x][j] - c[x] + sum < v) sum += a[x][j] - c[x], x = up[x][j];
        }
        return up[x][0];
    };     

    // Debugging
    /*
    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < k; j ++) cout << up[i][j] << ' ';
        cout << endl;
    }

    cout << endl;

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j < k; j ++) cout << a[i][j] << ' ';
        cout << endl;
    } 
    */

    // QUERY

    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