답안 #684041

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684041 2023-01-20T07:23:17 Z nifeshe 등산 경로 (IZhO12_route) C++17
100 / 100
155 ms 65536 KB
#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

route.cpp:8: warning: ignoring '#pragma comment ' [-Wunknown-pragmas]
    8 | #pragma comment (linker, "/STACK: 16777216")
      |
# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 39380 KB Output is correct
2 Correct 18 ms 39380 KB Output is correct
3 Correct 15 ms 39500 KB Output is correct
4 Correct 18 ms 39464 KB Output is correct
5 Correct 15 ms 39380 KB Output is correct
6 Correct 17 ms 39380 KB Output is correct
7 Correct 19 ms 39604 KB Output is correct
8 Correct 15 ms 39508 KB Output is correct
9 Correct 16 ms 39508 KB Output is correct
10 Correct 25 ms 42692 KB Output is correct
11 Correct 35 ms 44880 KB Output is correct
12 Correct 26 ms 42696 KB Output is correct
13 Correct 137 ms 65536 KB Output is correct
14 Correct 134 ms 65536 KB Output is correct
15 Correct 141 ms 65536 KB Output is correct
16 Correct 155 ms 65536 KB Output is correct
17 Correct 124 ms 65536 KB Output is correct
18 Correct 136 ms 65536 KB Output is correct
19 Correct 136 ms 65536 KB Output is correct
20 Correct 102 ms 65536 KB Output is correct