Submission #16908

# Submission time Handle Problem Language Result Execution time Memory
16908 2015-10-24T16:54:52 Z erdemkiraz Mountain Trek Route (IZhO12_route) C++
100 / 100
206 ms 42240 KB
#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 = (j + 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;

}
# Verdict Execution time Memory Grader output
1 Correct 0 ms 40788 KB Output is correct
2 Correct 0 ms 40788 KB Output is correct
3 Correct 0 ms 40788 KB Output is correct
4 Correct 0 ms 40788 KB Output is correct
5 Correct 0 ms 40788 KB Output is correct
6 Correct 0 ms 40788 KB Output is correct
7 Correct 0 ms 40788 KB Output is correct
8 Correct 0 ms 40788 KB Output is correct
9 Correct 0 ms 40788 KB Output is correct
10 Correct 12 ms 40788 KB Output is correct
11 Correct 24 ms 42240 KB Output is correct
12 Correct 21 ms 40788 KB Output is correct
13 Correct 186 ms 40788 KB Output is correct
14 Correct 177 ms 40788 KB Output is correct
15 Correct 206 ms 40788 KB Output is correct
16 Correct 201 ms 40788 KB Output is correct
17 Correct 136 ms 40788 KB Output is correct
18 Correct 169 ms 40788 KB Output is correct
19 Correct 174 ms 40788 KB Output is correct
20 Correct 142 ms 40788 KB Output is correct