oj.uz

Submission #539254

# Submission time Handle Problem Language Result Execution time Memory
539254 2022-03-18T15:45:04 Z DrearyJoke Fountain (eJOI20_fountain) C++17
100 / 100
 478 ms 38052 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

void solve(){
    int n, q;
    cin >> n >> q;
    vector<ll> A(n + 1), B(n + 1);
    for (int i = 1; i <= n; ++i) cin >> A[i] >> B[i];
    reverse(A.begin() + 1, A.end());
    reverse(B.begin() + 1, B.end());
    const int D = 20, val = 2e9;
    vector<vector<ll>> sum(n + 1, vector<ll>(D + 1));
    vector<vector<int>> parent(n + 1, vector<int>(D + 1));
    deque<int> d;
    B[0] = val;
    for (int i = 1; i <= n; ++i) {
        while (!d.empty() && A[i] >= A[d.back()]) d.pop_back();
        if (!d.empty()) sum[i][0] = B[d.back()], parent[i][0] = d.back();
        else sum[i][0] = val;
        d.push_back(i);
    }
    for (int j = 1; j <= D; ++j) {
        for (int i = 0; i <= n; ++i) {
            int p = parent[i][j - 1];
            sum[i][j] = sum[i][j - 1] + sum[p][j - 1];
            parent[i][j] = parent[p][j - 1];
        }
    }

    auto walk = [&] (int v, int dd) -> pair<ll, int> {
        int p = parent[v][0];
        ll s = sum[v][0];
        dd -= 1;
        for (int i = 0; i <= D; ++i) {
            if (dd & (1 << i)) s += sum[p][i], p = parent[p][i];
        }
        return {s, p};
    };
    auto bwalk = [&] (int v, ll c) -> int {
        int p = parent[v][0];
        ll s = sum[v][0];
        if (s >= c) return p;
        for (int i = D; i >= 0; --i) {
            if (s + sum[p][i] < c) {
                s += sum[p][i];
                p = parent[p][i];
            }
        }
        return parent[p][0];
    };
    // cout << "CHECKING: \n";
    // for (int i = 0; i <= n; ++i) cout << sum[i][D] << " ";
    // cout << endl;
    while (q--) {
        ll r, v;
        cin >> r >> v;
        r = n - r + 1;
        if (v <= B[r]) {
            cout << n - r + 1 << END;
            continue;
        }
        v -= B[r];
        // int lo = 1, hi = n - 1, ans = -1;
        // while (lo <= hi) {
        //     int mid = (lo + hi) / 2;
        //     auto [s, p] = walk(r, mid);
        //     if (s >= v) {
        //         ans = p;
        //         hi = mid - 1;
        //     } else {
        //         lo = mid + 1;
        //     }
        // }
        int ans = bwalk(r, v);
        // cout << "ANS: " << ans << END;
        // if (ans == -1) {
        //     cout << n - r + 1 << " wow " << v << " " << sum[r][D] << endl;
        // }
        // assert(ans != -1);
        if (ans == -1) {
            ans = 0;
        }
        ans = (ans ? n - ans + 1 : 0);
        cout << ans << END;
    }
}
int main()
{
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:50:10: warning: variable 'walk' set but not used [-Wunused-but-set-variable]
   50 |     auto walk = [&] (int v, int dd) -> pair<ll, int> {
      |          ^~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 32700 KB Output is correct
2 Correct 329 ms 30340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 359 ms 32700 KB Output is correct
9 Correct 329 ms 30340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 165 ms 19072 KB Output is correct
12 Correct 478 ms 34844 KB Output is correct
13 Correct 362 ms 38052 KB Output is correct
14 Correct 216 ms 37276 KB Output is correct
15 Correct 162 ms 37580 KB Output is correct