oj.uz

Submission #16893

# Submission time Handle Problem Language Result Execution time Memory
16893 2015-10-24T13:03:32 Z murat Mountain Trek Route (IZhO12_route) C++
60 / 100
 539 ms 6784 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5628 KB Output is correct
2 Correct 0 ms 5628 KB Output is correct
3 Correct 0 ms 5628 KB Output is correct
4 Correct 0 ms 5628 KB Output is correct
5 Correct 0 ms 5628 KB Output is correct
6 Correct 0 ms 5628 KB Output is correct
7 Correct 0 ms 5628 KB Output is correct
8 Correct 0 ms 5628 KB Output is correct
9 Correct 0 ms 5628 KB Output is correct
10 Correct 20 ms 5628 KB Output is correct
11 Correct 20 ms 6784 KB Output is correct
12 Correct 539 ms 6784 KB Output is correct
13 Runtime error 152 ms 5624 KB SIGSEGV Segmentation fault
14 Runtime error 177 ms 5624 KB SIGSEGV Segmentation fault
15 Runtime error 145 ms 5624 KB SIGSEGV Segmentation fault
16 Runtime error 160 ms 5624 KB SIGSEGV Segmentation fault
17 Runtime error 154 ms 5624 KB SIGSEGV Segmentation fault
18 Runtime error 177 ms 5624 KB SIGSEGV Segmentation fault
19 Runtime error 187 ms 5624 KB SIGSEGV Segmentation fault
20 Runtime error 150 ms 5624 KB SIGSEGV Segmentation fault