Submission #16906

#	Time	Username	Problem	Language	Result	Execution time	Memory
16906		erdemkiraz	Mountain Trek Route (IZhO12_route)	C++98	95 / 100	183 ms	42240 KiB

route

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
#define end ____end

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 2e6 + 5;

int n, k, ans;
int a[N], root[N], beg[N], end[N], val[N];

int f(int x) {
    if(x == root[x])
        return x;
    return root[x] = f(root[x]);
}

void merge(int x, int y) {
    x = f(x);
    y = f(y);
    if(val[x] != val[y])
        return;
    root[y] = x;
    beg[x] = min(beg[x], beg[y]);
    end[x] = max(end[x], end[y]);
}

int main() {

    scanf("%d %d", &n, &k);

    for(int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }

    int ind = max_element(a, a + n) - a;

    for(int i = 0; i < ind; i++)
        a[i + n] = a[i];

    for(int i = 0; i < n; i++)
        a[i] = a[i + ind];

    set < ii > s;

    val[0] = a[0];
    root[n] = 0;

    for(int i = 1; i < n; i++) {
        int j = i;
        while(j + 1 < n and a[j + 1] == a[i])
            j++;
        for(int k = i; k <= j; k++)
            root[k] = i;
        val[i] = a[i];
        beg[i] = i;
        end[i] = j;
        int l = i - 1;
        int r = (i + 1) % n;
        if(a[i] < a[l] and a[i] < a[r]) {
            s.insert(ii(j - i + 1, i));
        }
        i = j;
    }

    while(s.size()) {
        int len = s.begin() -> first;
        if(k < len)
            break;
        int x = s.begin() -> second;
        s.erase(s.begin());
        int i = beg[x];
        int j = end[x];
        int l = val[f(i - 1)];
        int r = val[f(j + 1)];
        int p = min(k / len, min(l, r) - val[x]);
        k -= p * len;
        ans += p * 2;
        val[x] += p;
        if(i - 1 > 0) {
            merge(x, i - 1);
        }
        if(j + 1 < n) {
            merge(x, j + 1);
        }
        i = beg[x];
        j = end[x];
        l = val[f(i - 1)];
        r = val[f(j + 1)];
        if(val[x] < l and val[x] < r) {
            s.insert(ii(j - i + 1, x));
        }
    }

    printf("%d\n", ans);

    return 0;

}

• Subtask 1: 95 / 100