Submission #16907

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16907	2015-10-24T16:49:40 Z	erdemkiraz	Mountain Trek Route (IZhO12_route)	C++	95 / 100	191 ms	42240 KB

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];

    assert(max_element(a, a + n) == a);

    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]);
        assert(p);
        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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	40788 KB	Output is correct
2	Incorrect	0 ms	40788 KB	Output isn't 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	17 ms	40788 KB	Output is correct
11	Correct	26 ms	42240 KB	Output is correct
12	Correct	23 ms	40788 KB	Output is correct
13	Correct	191 ms	40788 KB	Output is correct
14	Correct	173 ms	40788 KB	Output is correct
15	Correct	117 ms	40788 KB	Output is correct
16	Correct	167 ms	40788 KB	Output is correct
17	Correct	150 ms	40788 KB	Output is correct
18	Correct	156 ms	40788 KB	Output is correct
19	Correct	156 ms	40788 KB	Output is correct
20	Correct	137 ms	40788 KB	Output is correct