Submission #659537

#	Time	Username	Problem	Language	Result	Execution time	Memory
659537		illyakr	Fountain (eJOI20_fountain)	C++14	100 / 100	624 ms	40760 KiB

fountain

#include <iostream>
#define int long long

using namespace std;

struct Info {
    int d, c;
};
int n, q;
Info a[101010];
int t[401010];
void build(int v, int vl, int vr) {
    if (vl == vr) {
        t[v] = a[vl].d;
        return;
    }
    int vm = (vl + vr) / 2;
    build(2 * v, vl, vm);
    build(2 * v + 1, vm + 1, vr);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
int gt(int v, int vl, int vr, int l, int r) {
    if (l <= vl && vr <= r)return t[v];
    if (r < vl || vr < l)return 0;
    int vm = (vl + vr) / 2;
    return max(gt(2 * v, vl, vm, l, r), gt(2 * v + 1, vm + 1, vr, l, r));
}
int to[101010];
int L[101010];
int rmq[30][101010];
int sum[30][101010];
bool used[101010];
void dfs(int v, int pred) {
    if (used[v])return;
    used[v] = true;

    if (v == n) {
        for (int i = 0; i <= L[n]; i++) {
            rmq[i][v] = n;
            sum[i][v] = 1010101010;
        }
        return;
    }
    rmq[0][v] = to[v];
    sum[0][v] = a[v].c;
//    cout << v << " " << pred << " ------  " << rmq[0][v] << " " << sum[0][v] << endl;

    dfs(to[v], v);
    for (int i = 1; i <= L[n]; i++) {
        sum[i][v] = sum[i - 1][v] + sum[i - 1][rmq[i - 1][v]];
        rmq[i][v] = rmq[i - 1][rmq[i - 1][v]];
    }
}


int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i].d >> a[i].c;
    n++;
    a[n] = {1010101010, 1010101010};
    build(1, 1, n);
    for (int i = n; i >= 1; i--) {
        int l = 0, r = n - i;
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            int cur = gt(1, 1, n, i + 1, i + mid);
            if (cur > a[i].d)r = mid;
            else l = mid;
        }
        to[i] = i + r;
    }
    L[1] = 0;
    for (int i = 2; i <= n; i++) {
        L[i] = L[i / 2] + 1;
    }
    for (int i = 1; i <= n; i++) {
        if (used[i])continue;
        dfs(i, i);
    }
//    for (int i = 1; i <= n; i++) {
//        cout << i << " ------------------ \n";
//        for (int j = 0; j <= L[n]; j++) {
//            cout << rmq[j][i] << " " << sum[j][i] << endl;
//        }
//        cout << endl;
//    }

    for (int id = 1; id <= q; id++) {
        int r, v;
        cin >> r >> v;
        for (int i = L[n]; i >= 0; i--) {
            if (sum[i][r] >= v)continue;
            v -= sum[i][r];
            r = rmq[i][r];
        }
        cout << (r == n ? 0 : r) << '\n';
    }
}
/**
6 5
4 10
6 8
3 5
4 14
10 9
4 20
1 25
6 30
5 8
3 13
2 8
*/

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