Submission #484152

#	Time	Username	Problem	Language	Result	Execution time	Memory
484152		FatihSolak	Mountain Trek Route (IZhO12_route)	C++17	100 / 100	117 ms	29416 KiB

route

#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n,k;
int val[N];
int par[N];
int l[N],r[N];
int len[N];
int find(int a){
    if(par[a] == a)return a;
    return par[a] = find(par[a]);
}
void merge(int a,int b){
    a = find(a);
    b = find(b);
    if(a == b)return;
    if(val[a] != val[b])return;
    par[b] = a;
    r[a] = r[b];
    len[a] += len[b];
    len[b] = 0;         
}
bool ck(int x){
    if(len[x] == 0)return 0;
    if(val[find((l[x] - 1 + n)%n)] <= val[x])return 0;
    if(val[find((r[x] + 1 + n)%n)] <= val[x])return 0;
    return 1;
}
void solve(){
    cin >> n >> k;
    for(int i=0;i<n;i++){
        par[i] = l[i] = r[i] = i;
        len[i] = 1;
        cin >> val[i];
    }
    for(int i=0;i<n;i++){
        merge(i, (i + 1)%n);
    }
    set<pair<int,int>> s;
    for(int i=0;i<n;i++){
        if(ck(i)){
            s.insert({len[i],i});
        }
    }
    long long ans = 0;
    while(s.size() && k >= s.begin()->first){
        auto [ln,x] = *s.begin();
        s.erase(s.begin());
        int num = min(val[find((l[x] - 1 + n)%n)]-val[x],val[find((r[x] + 1 + n)%n)] - val[x]);
        num = min(num,k/ln);
        val[x] += num;
        k -= num*ln;
        //cout << x << " " << l[x] << " " << r[x] << " " << len[x] <<" " << val[x]<< endl;
        merge((l[x] - 1 + n)%n,x);
        merge(x,(r[x] + 1 + n)%n);
        x = find(x);
        if(ck(x)){
            s.insert({len[x],x});
        }
        ans += num * 2;
    }
    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

• Subtask 1: 100 / 100