oj.uz

Submission #539248

# Submission time Handle Problem Language Result Execution time Memory
539248 2022-03-18T15:36:49 Z DrearyJoke Fountain (eJOI20_fountain) C++17
0 / 100
 105 ms 66044 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) {
            sum[i][j] = sum[i][j - 1] + sum[parent[i][j - 1]][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};
    };

    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;
            }
        }
        // cout << "ANS: " << ans << END;
        // if (ans == -1) {
        //     cout << n - r + 1 << " wow " << v << " " << sum[r][D] << endl;
        // }
        assert(ans != -1);
        ans = (ans ? n - ans + 1 : 0);
        cout << ans << END;
    }
}
int main()
{
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 2 ms 852 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 105 ms 66044 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Runtime error 2 ms 852 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -