oj.uz

답안 #853276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
853276 2023-09-23T20:50:57 Z heartbeat Fountain (eJOI20_fountain) C++14
0 / 100
 146 ms 28520 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct Tree {
    int sz = 1;
    vector<vector<int>> table;
    vector<vector<ll>> sum;
    Tree (){}
    Tree (int n) {
        while ((1 << sz) <= n) sz++;
        table = vector<vector<int>> (sz, vector<int> ((1 << sz)));
        sum = vector<vector<ll>> (sz, vector<ll> ((1 << sz)));
    }
    void add_cost(int u, int x) {
        sum[0][u] = x;
    }
    void add_edge(int u, int v) {
        table[0][u] = v;
    }
    void build() {
        for (int bit = 1; bit < sz; ++bit) {
            for (int Node = 1; Node < sz; ++Node) {
                int to = table[bit - 1][Node];
                table[bit][Node] = table[bit - 1][to];
                sum[bit][Node] = sum[bit - 1][Node] + sum[bit - 1][to];
            }
        }
    }
    pair<int, ll> get_kth(int Node, int k) {
        ll ret = 0;
        for (int i = sz - 1; i >= 0; --i) {
            if (k & (1 << i)) {
                ret += sum[i][Node];
                Node = table[i][Node];
            }
        }
        return make_pair(Node, ret + sum[0][Node]);
    }
};
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q, idx = 1;
    cin >> n >> q;
    Tree tree(n);
    vector<pair<int, int>> v(n);
    for (auto &[a, b] : v) {
        cin >> a >> b;
        tree.add_cost(idx++, b);
    }
    vector<int> track;
    for (int i = n - 1; i >= 0; --i) {
        while (track.size() && v[track.back()].first <= v[i].first) {
            track.pop_back();
        }
        if (track.size()) {
            tree.add_edge(i + 1, track.back() + 1);
        }
        track.push_back(i);
    }
    tree.build();
    for (int i = 0, start, x; i < q; ++i) {
        cin >> start >> x;
        int l = 0;
        int r = n;
        int best = 0;
        while (l <= r) {
            int mid = (l + r) / 2;
            auto [who, path] = tree.get_kth(start, mid);
            if (path >= x) {
                best = who;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        cout << best << '\n';
    }
    return 0;
}
/*
*/

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:47:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto &[a, b] : v) {
      |                ^
fountain.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |             auto [who, path] = tree.get_kth(start, mid);
      |                  ^

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 146 ms 28520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -