Submission #876064

#	Time	Username	Problem	Language	Result	Execution time	Memory
876064		The_Samurai	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	713 ms	65536 KiB

route

// 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(3 * 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: 0 / 100