Submission #16893

#	Time	Username	Problem	Language	Result	Execution time	Memory
16893		murat	Mountain Trek Route (IZhO12_route)	C++98	60 / 100	539 ms	6784 KiB

route

#include <bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;

int cost, n, m, x, y, val[N], root[N], L[N], R[N], a[N], t, k, ans;

int next(int x) { return x == n ? 1 : x + 1; }
int prev(int x) { return x == 1 ? n : x - 1; }

int length(int x, int y) {
    if(x < y) return y - x + 1;
    return y + n - x + 1;
}

int findset(int x) { return root[x] = root[x] == x ? x : findset(root[x]); }

void merge(int x, int y) {
    if((x = findset(x)) == (y = findset(y))) return ;
    val[x] = max(val[x], val[y]);
    root[y] = x;
    R[x] = R[y];
}

int main() {

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

    FOR(i, 1, n)
        scanf("%d",&a[i]);

    FOR(i, 1, n) {
        root[i] = L[i] = R[i] = i;
        val[i] = a[i];
    }

    priority_queue< pair< int , pii > , vector< pair< int , pii > > , greater< pair< int , pii > > > q;

    FOR(i, 1, n) {
        if(a[prev(i)] >= a[i] && a[next(i)] >= a[i]) {
            q.push(mp(1, mp(i, i)));
        }
    }

    while(!q.empty()) {
        x = q.top().nd.st;
        y = q.top().nd.nd;
        cost = q.top().st;
        q.pop();
        if(cost > k || length(x, y) == n) continue;
        int l = val[findset(prev(x))];
        int r = val[findset(next(y))];
        int ddd = min(l, r);
        if(k < cost * (ll) (ddd - val[findset(x)]))
            ddd = val[findset(x)] + (k / cost);
        ans += (ddd - val[findset(x)]) * 2;
        k -= (ddd - val[findset(x)]) * cost;
        val[findset(x)] = ddd;
        if(l == ddd)  merge(prev(x), x);
        if(r == ddd) merge(x, next(y));
        x = L[findset(x)], y = R[findset(x)];
        if(val[findset(prev(x))] >= val[findset(x)] && val[findset(next(y))] >= val[findset(x)] && length(x, y) > cost)
            q.push(mp(length(x, y), mp(x, y)));
    }

    cout << ans << endl;

    return 0;
}                 

• Subtask 1: 60 / 100