제출 #539254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
539254		DrearyJoke	Fountain (eJOI20_fountain)	C++17	100 / 100	478 ms	38052 KiB

fountain

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40