oj.uz

Submission #339885

# Submission time Handle Problem Language Result Execution time Memory
339885 2020-12-26T10:29:52 Z fixikmila Mountain Trek Route (IZhO12_route) C++14
0 / 100
 128 ms 28524 KB 
#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[100000];
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

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 15 ms 3948 KB Output is correct
11 Correct 16 ms 4592 KB Output is correct
12 Correct 14 ms 3948 KB Output is correct
13 Incorrect 128 ms 28524 KB Output isn't correct
14 Halted 0 ms 0 KB -