Submission #684041

#	Time	Username	Problem	Language	Result	Execution time	Memory
684041		nifeshe	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	155 ms	65536 KiB

route

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e18;
const int MAX = 1e6 + 5;
const int LG = 31;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

vector<int> p(MAX), l(MAX), r(MAX), siz(MAX), val(MAX);
int m = 0;
int n;

void create(int x, int v) {
    p[x] = l[x] = r[x] = x;
    siz[x] = 1;
    val[x] = v;
    m++;
}

int get(int x) {
    return p[x] = (p[x] == x? x : get(p[x]));
}

void unite(int x, int y) {
    x = get(x), y = get(y);
    if(x != y) {
        val[x] = val[y];
        if(siz[x] < siz[y]) swap(x, y);
        if(r[x] >= n) {
            if(r[y] + 1 == l[x]) l[x] = l[y];
            else if(r[x] % n + 1 == l[y]) r[x] = r[y] + n;
        }
        else if(r[y] >= n) {
            if(r[x] + 1 == l[y]) l[y] = l[x];
            else if(r[y] % n + 1 == l[x]) r[y] = r[x] + n;
            swap(l[x], l[y]);
            swap(r[x], r[y]);
        }
        else if(r[x] + 1 != l[y] && r[y] + 1 != l[x]) {
            if(r[x] == n - 1) r[x] = r[y] + n;
            else {
                l[x] = l[y];
                r[x] += n;
            }
        }
        else {
            umin(l[x], l[y]);
            umax(r[x], r[y]);
        }
        siz[x] += siz[y];
        p[y] = x;
        m--;
    }
}

void solve() {
    int k;
    cin >> n >> k;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }
    int ans = 0;
    for(int i = 0; i < n; i++) create(i, a[i]);
    for(int i = 1; i < n; i++) {
        if(a[i] == a[i - 1]) unite(i, i - 1);
    }
    if(a[0] == a[n - 1]) unite(0, n - 1);
    set<pair<int, int>> best;
    vector<int> v(n);
    vector<int> was(n, 0);
    for(int i = 0; i < n; i++) {
        if(was[get(i)]) continue;
        int ok = 1;
        int L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
        if(a[i] >= a[R]) ok = 0;
        if(a[i] >= a[L]) ok = 0;
        if(ok) {
            best.insert({siz[get(i)], get(i)});
            v[get(i)] = siz[get(i)];
        }
        was[get(i)] = 1;
    }
    while(sz(best) && k) {
        int i = (*best.begin()).s; best.erase(best.begin());
        if(siz[get(i)] > k) continue;
        if(siz[get(i)] == n) break;
        int L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
        int d = inf;
        umin(d, val[get(R)] - val[get(i)]);
        umin(d, val[get(L)] - val[get(i)]);
        umin(d, k / siz[get(i)]);
        ans += 2 * d;
        k -= d * siz[get(i)];
        val[get(i)] += d;
        if(val[get(i)] == val[get(R)]) {
            best.erase({v[get(R)], get(R)});
            unite(i, R);
        }
        if(val[get(i)] == val[get(L)]) {
            best.erase({v[get(L)], get(L)});
            unite(i, L);
        }
        L = (l[get(i)] - 1 + n) % n, R = (r[get(i)] + 1) % n;
        int ok = 1;
        if(val[get(i)] >= val[get(R)]) ok = 0;
        if(val[get(i)] >= val[get(L)]) ok = 0;
        if(ok) {
            best.insert({siz[get(i)], get(i)});
            v[get(i)] = siz[get(i)];
        }
    }
    cout << ans << '\n';
}

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Compilation message (stderr)

route.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |

• Subtask 1: 100 / 100