Submission #562582

#	Time	Username	Problem	Language	Result	Execution time	Memory
562582		illyakr	Fountain (eJOI20_fountain)	C++14	100 / 100	454 ms	64204 KiB

fountain

//#pragma GCC optimize("inline,Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,popcnt,avx,abm")
#include <bits/stdc++.h>
#define ll long long
#define int ll
typedef long double ld;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define y0 dfgoert
#define y1 kjsjofd
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mod = 1000000007;
const int INF1e9 = 1010101010;
const int INF1e18 = 1010101010101010101;
const ld PI =  3.14159265358979323846264338327950288419716939937510;

int n, q;
int d[101010], c[101010];
int t[401010];
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = vl;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    if (d[t[2 * v]] > d[t[2 * v + 1]])
        t[v] = t[2 * v];
    else
        t[v] = t[2 * v + 1];
}

int gt(int v, int vl, int vr, int l, int r, int cur) {
    if (d[t[v]] <= cur)return INF1e9;
    if (vl == vr)return t[v];

    int vm = (vl + vr) / 2;
    if (l <= vl && vr <= r) {
        if (cur < d[t[2 * v]])return gt(2 * v, vl, vm, l, r, cur);
        return gt(2 * v + 1, vm + 1, vr, l, r, cur);
    }
    if (r < vl || vr < l)return INF1e9;
    return min(gt(2 * v, vl, vm, l, r, cur), gt(2 * v + 1, vm + 1, vr, l, r, cur));
}
vector<pair<int, int> > g[101010];
int rmq[30][101010];
int can[30][101010];
int to[101010];

int tin[101010];
int tout[101010];
int T = 1;
void dfs(int v) {
    if (tin[v] != 0)return;
    tin[v] = T++;
//    cout << v << " --> " << to[v] << endl;
    if (to[v] == 0) {
        for (int i = 0; i < 30; i++) {
            rmq[i][v] = v;
            can[i][v] = INF1e9;
        }
        return;
    }
    dfs(to[v]);
    tout[v] = T++;

    rmq[0][v] = to[v];
    can[0][v] = c[v];

    for (int i = 1; i < 30; i++) {
        rmq[i][v] = rmq[i - 1][rmq[i - 1][v]];
        can[i][v] = can[i - 1][v] + can[i - 1][rmq[i - 1][v]];
    }
}

int uplf(int v, int li) {
//    cout << v << " " << li << " !!" << endl;
    for (int i = 29; i >= 0; i--) {
//        cout << i << ": " << can[i][v] << "   " << rmq[i][v] << "      ??? " << li << endl;
        if (li > can[i][v]) {
            li -= can[i][v];
            v = rmq[i][v];
            continue;
        }
    }
    return v;
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> d[i] >> c[i];
    d[n + 1] = INF1e18;c[n + 1] = INF1e18;
    n++;

    build(1, 1, n);
    for (int i = n - 1; i >= 1; i--) {
        to[i] = gt(1, 1, n, i + 1, n, d[i]);
    }
    dfs(1);
    for (int i = 1; i <= n; i++) {
        if (tin[i] == 0)
            dfs(i);
    }
    while (q--) {
        int R, V;
        cin >> R >> V;
        int ans = uplf(R, V);
        if (ans == n)cout << 0 << '\n';
        else cout << ans << '\n';
    }
//    for (int i = 1; i <= n; i++) {
//        for (int j = 0; j < 5; j++) {
//            cout << setw(2) << rmq[j][i];
//            cout << setw(5) << can[j][i];
//            cout << "        ";
//        }
//        cout << endl;
//    }
}

int32_t main() {
    fast
    int t = 1;
//    cin >> t;
    for (int id = 1; id <= t; id++) {
//        cout << "Case " << id << ": ";
        solve();
    }
}
/**
10 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10


6 5
4 10
6 8
3 5
4 14
10 9
4 20
*/

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