oj.uz

답안 #339885

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339885 2020-12-26T10:29:52 Z fixikmila 등산 경로 (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

# 결과 실행 시간 메모리 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 -