oj.uz

답안 #876066

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876066 2023-11-21T07:53:16 Z The_Samurai 등산 경로 (IZhO12_route) C++17
100 / 100
 684 ms 63812 KB 
// I stand with PALESTINE




//#pragma GCC optimize("Ofast,O3")
//#pragma GCC target("avx,avx2")
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int inf = 1e9;

struct segtree {
    vector<int> tree;
    int size;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size - 1, 0);
    }

    void set(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = v;
            return;
        }
        int m = (lx + rx) >> 1;
        if (i < m) set(i, v, 2 * x + 1, lx, m);
        else set(i, v, 2 * x + 2, m, rx);
        tree[x] = tree[2 * x + 1] + tree[2 * x + 2];
    }

    void set(int i, int v) {
        set(i, v, 0, 0, size);
    }

    int get_sum(int l, int r, int x, int lx, int rx) {
        if (l >= rx or lx >= r) return 0;
        if (l <= lx and rx <= r) return tree[x];
        int m = (lx + rx) >> 1;
        return get_sum(l, r, 2 * x + 1, lx, m) + get_sum(l, r, 2 * x + 2, m, rx);
    }

    int get_sum(int l, int r) {
        return get_sum(l, r + 1, 0, 0, size);
    }

    int get(int v, int x, int lx, int rx) {
        if (rx - lx == 1) return tree[x] ? lx : -1;
        int m = (lx + rx) >> 1;
        if (tree[2 * x + 1] >= v) return get(v, 2 * x + 1, lx, m);
        else return get(v - tree[2 * x + 1], 2 * x + 2, m, rx);
    }

    int get(int v) {
        return get(v, 0, 0, size);
    }
};

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(3 * n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[2 * n + i] = a[n + i] = a[i];
    }
    vector<int> left(n), right(n);
    stack<int> s;
    for (int i = 0; i < 2 * n; i++) {
        while (!s.empty() and a[s.top()] <= a[i]) s.pop();
        if (n <= i and i < 2 * n) left[i - n] = s.empty() ? -1 : s.top();
        s.push(i);
    }
    while (!s.empty()) s.pop();
    for (int i = 3 * n - 1; i >= n; i--) {
        while (!s.empty() and a[s.top()] <= a[i]) s.pop();
        if (n <= i and i < 2 * n) right[i - n] = s.empty() ? 3 * n : s.top();
        s.push(i);
    }
    while (!s.empty()) s.pop();

    segtree sg; sg.init(n);
    vector<pair<int, int>> v;
    for (int i = 0; i < 3 * n; i++) sg.set(i, 1);
    for (int i = n; i < 2 * n; i++) v.emplace_back(a[i], i);
    sort(v.begin(), v.end());
    vector<pair<int, int>> val;
    for (auto [x, i]: v) {
        if (!sg.get_sum(i - n, i - n)) continue;
        if (left[i - n] == -1 and right[i - n] == 3 * n) break;
        int dist, mn;
        if (left[i - n] < n) {
            right[i - n] %= n;
            int next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            while (next != -1) {
                sg.set(next, 0);
                next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            }
            next = sg.get(1);
            while (next != -1 and next < right[i - n]) {
                sg.set(next, 0);
                next = sg.get(1);
            }
            dist = (n - left[i - n] - 1) + right[i - n];
        } else if (right[i - n] >= 2 * n) {
            left[i - n] %= n; right[i - n] %= n;
            int next = sg.get(1);
            while (next != -1 and next < right[i - n]) {
                sg.set(next, 0);
                next = sg.get(1);
            }
            next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            while (next != -1) {
                sg.set(next, 0);
                next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            }
            dist = right[i - n] + (n - left[i - n] - 1);
        } else {
            left[i - n] %= n; right[i - n] %= n;
            int next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            while (next != -1 and next < right[i - n]) {
                sg.set(next, 0);
                next = sg.get(sg.get_sum(0, left[i - n]) + 1);
            }
            dist = right[i - n] - left[i - n] - 1;
        }
        mn = min(a[left[i - n] % n], a[right[i - n] % n]);
        val.emplace_back(dist, mn - a[i - n]);
    }
    sort(val.begin(), val.end());
    int ans = 0;
    for (auto [cost, cnt]: val) {
        if (1ll * cost * cnt <= k) {
            ans += cnt;
            k -= cost * cnt;
        } else {
            ans += k / cost;
            break;
        }
    }
    cout << ans * 2;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
#ifdef sunnatov
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int q = 1;
    //    cin >> q;
    while (q--) {
        solve();
        cout << '\n';
    }
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 64 ms 5912 KB Output is correct
11 Correct 118 ms 5624 KB Output is correct
12 Correct 59 ms 4972 KB Output is correct
13 Correct 636 ms 63656 KB Output is correct
14 Correct 649 ms 63812 KB Output is correct
15 Correct 629 ms 61672 KB Output is correct
16 Correct 637 ms 62868 KB Output is correct
17 Correct 684 ms 62536 KB Output is correct
18 Correct 645 ms 63560 KB Output is correct
19 Correct 634 ms 63576 KB Output is correct
20 Correct 572 ms 50928 KB Output is correct