oj.uz

Submission #659537

# Submission time Handle Problem Language Result Execution time Memory
659537 2022-11-18T12:05:20 Z illyakr Fountain (eJOI20_fountain) C++14
100 / 100
 624 ms 40760 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 37632 KB Output is correct
2 Correct 474 ms 35192 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 474 ms 37632 KB Output is correct
9 Correct 474 ms 35192 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 215 ms 19456 KB Output is correct
12 Correct 624 ms 40760 KB Output is correct
13 Correct 511 ms 37196 KB Output is correct
14 Correct 413 ms 36456 KB Output is correct
15 Correct 402 ms 36712 KB Output is correct