oj.uz

답안 #539253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
539253 2022-03-18T15:42:30 Z DrearyJoke Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 38580 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};
    };
    // 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;
            }
        }
        // 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;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 2 ms 584 KB Output is correct
5 Correct 3 ms 596 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1230 ms 32712 KB Output is correct
2 Correct 1383 ms 33396 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 2 ms 584 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1230 ms 32712 KB Output is correct
9 Correct 1383 ms 33396 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 506 ms 20852 KB Output is correct
12 Execution timed out 1549 ms 38580 KB Time limit exceeded
13 Halted 0 ms 0 KB -