Submission #339890

#	Time	Username	Problem	Language	Result	Execution time	Memory
339890		fixikmila	Mountain Trek Route (IZhO12_route)	C++14	100 / 100	140 ms	32236 KiB

route

#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll>pll;
typedef long double ld;
ll bin_pow(ll a,ll b){
    if(b==0)return 1;
    if(b%2==0){
        ll t=bin_pow(a,b/2);
        return t*t%MOD;
    }
    else return a*bin_pow(a,b-1)%MOD;
}
vector<ll>a,l,r;
int link[1000000],sz[1000000];
int get(int x){
    if(x==link[x])return x;
    return link[x]=get(link[x]);
}
void unite(int x,int y){
    x=get(x);
    y=get(y);
    //if(sz[x]<sz[y])swap(x,y);
    if(x==y)return;
    link[y]=x;
    sz[x]+=sz[y];
    r[x]=r[y];
    l[y]=l[x];
}
int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
    cin>>n>>k;
    a.resize(n);
    l.resize(n);
    r.resize(n);
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++){
        if(i==0)l[i]=n-1;
        else l[i]=i-1;
        if(i==n-1)r[i]=0;
        else r[i]=i+1;
        sz[i]=1;
        link[i]=i;
    }
    for(int i=0;i<n;i++){
        if(a[i]==a[r[i]])unite(i,r[i]);
    }
    priority_queue<pair<int,int>>q;
    for(int i=0;i<n;i++){
        if(link[i]==i&&a[i]<min(a[get(l[i])],a[get(r[i])]))q.push({-sz[i],i});
    }
    while(!q.empty()){
        x=q.top().second;
        q.pop();
        x=get(x);
        y=min(a[get(l[x])],a[get(r[x])])-a[x];
        if(y*sz[x]<=k){
               // cout<<y<<" "<<sz[x]<<" "<<a[x]<<endl;
            k-=y*sz[x];
        //cout<<k<<endl;
            ans+=2*y;
            a[x]+=y;
            if(a[x]==a[get(l[x])])unite(l[x],x);
            if(a[x]==a[get(r[x])])unite(x,r[x]);
            x=get(x);
            //a[x]+=y;
            //cout<<x<<" "<<a[x]<<" "<<sz[x]<<" "<<a[get(l[x])]<<endl;
            if(a[x]<min(a[get(l[x])],a[get(r[x])]))q.push({-sz[x],x});
        }
        else{
            ans+=2*(k/sz[x]);
            break;
        }
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

route.cpp: In function 'int main()':
route.cpp:37:8: warning: unused variable 't' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
route.cpp:37:14: warning: unused variable 'm' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |              ^
route.cpp:37:20: warning: unused variable 'sum' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
route.cpp:37:35: warning: unused variable 'z' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                   ^
route.cpp:37:45: warning: unused variable 'mn' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                             ^~
route.cpp:37:58: warning: unused variable 'mx' [-Wunused-variable]
   37 |     ll t=1,n,m,k=0,sum=0 ,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                          ^~

• Subtask 1: 100 / 100