oj.uz

답안 #340027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
340027 2020-12-26T15:32:32 Z scales 등산 경로 (IZhO12_route) C++17
100 / 100
 153 ms 44652 KB 
#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
long long c[1000000],a[1000000],l[1000000],r[1000000],d[1000000];
long long fun(long long x)
{
    if(c[x]==x)
    {
        return x;
    }
    else
    {
        c[x]=fun(c[x]);
        return c[x];
    }
}
void un(long long x,long long y)
{
    x=fun(x);
    y=fun(y);
    r[x]=r[y];
    d[x]=d[x]+d[y];
    c[y]=x;
}
int main()
{
      ios::sync_with_stdio(false);
      cin.tie(0);
     // freopen("input.txt","r",stdin);
     // freopen("output.txt","w",stdout);
     long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
     cin>>n;
     cin>>k;
     priority_queue  <pair<long long,long long> > q;
     x1=0;
     sum=0;
     for(i=0;i<n;i++)
     {
         cin>>a[i];
         c[i]=i;
         d[i]=1;
         l[i]=i;
         r[i]=i;
         if(i!=0 && a[i]==a[i-1])
         {
             un(i-1,i);
         }
     }
     if(a[0]==a[n-1])
     {
         un(n-1,0);
     }
     for(i=0;i<n;i++)
     {
         if(fun(i)==i)
         {
              x=fun(i);
              f=l[x]-1;
              if(f==-1)
              {
                   f=n-1;
              }
              f=fun(f);
              s=r[x]+1;
              if(s==n)
              {
                  s=0;
              }
              s=fun(s);
              if(a[x]<a[f] && a[x]<a[s])
              {
                 //cout<<"i="<<i<<endl;
                  q.push({-d[x],x});
              }
         }
     }

     while(!q.empty())
     {
         x=q.top().first;
         y=q.top().second;
         //cout<<"x="<<x<<" y="<<y<<" ";
         q.pop();
         x=fun(y);
       // cout<<"x="<<x<<" a[x]="<<a[x]<<endl;

         f=l[x]-1;
         if(f==-1)
         {
             f=n-1;
         }
         f=fun(f);

         s=r[x]+1;
         if(s==n)
         {
             s=0;
         }
         s=fun(s);
        //cout<<"f="<<f<<" s="<<s<<" ";
         kol=min(a[f]-a[x],a[s]-a[x]);
         v=d[x];
         //cout<<"v="<<v<<" ";
         if(v*kol<=k)
         {
            a[x]=a[x]+kol;
            k=k-kol*v;
            x1=x1+2*kol;
         }
         else
         {
             kol=k/v;
             k=0;
             a[x]=a[x]+kol;
              x1=x1+2*kol;
         }
         //cout<<"kol="<<kol<<" k="<<k<<endl;
         if(k==0)
         {
             break;
         }
         if(a[x]==a[f])
         {
             un(f,x);
         }
         if(a[x]==a[s])
         {
             un(x,s);
         }
         x=fun(x);
         f=l[x]-1;
         if(f==-1)
         {
             f=n-1;
         }
         f=fun(f);

         s=r[x]+1;
         if(s==n)
         {
             s=0;
         }
         s=fun(s);
         if(a[x]<a[s] && a[x]<a[f])
         {
             q.push({-d[x],x});
         }

     }
     cout<<x1;
    return 0;
}

Compilation message

route.cpp: In function 'int main()':
route.cpp:36:16: warning: unused variable 't' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                ^
route.cpp:36:20: warning: unused variable 'j' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                    ^
route.cpp:36:22: warning: unused variable 'dno' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                      ^~~
route.cpp:36:26: warning: unused variable 'mini' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                          ^~~~
route.cpp:36:35: warning: unused variable 'm' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                   ^
route.cpp:36:46: warning: unused variable 'tip' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                              ^~~
route.cpp:36:50: warning: unused variable 'g' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                                  ^
route.cpp:36:52: warning: unused variable 'maxi' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                                    ^~~~
route.cpp:36:57: warning: unused variable 'p' [-Wunused-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                                         ^
route.cpp:36:63: warning: variable 'sum' set but not used [-Wunused-but-set-variable]
   36 |      long long t,i,j,dno,mini,x,y,m,k,v,n,x1,tip,g,maxi,p,kol,sum,f,s;
      |                                                               ^~~

Subtask #1
100.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 0 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 14 ms 5100 KB Output is correct
11 Correct 17 ms 6380 KB Output is correct
12 Correct 14 ms 5228 KB Output is correct
13 Correct 137 ms 44140 KB Output is correct
14 Correct 137 ms 44396 KB Output is correct
15 Correct 127 ms 44268 KB Output is correct
16 Correct 129 ms 44196 KB Output is correct
17 Correct 129 ms 44396 KB Output is correct
18 Correct 138 ms 44396 KB Output is correct
19 Correct 153 ms 44268 KB Output is correct
20 Correct 115 ms 44652 KB Output is correct