Submission #340026

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
340026	2020-12-26T15:28:31 Z	scales	Mountain Trek Route (IZhO12_route)	C++17	0 / 100	1 ms	364 KB

route

#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=r[x]-l[x]+1;
         //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

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	Incorrect	1 ms	364 KB	Output isn't correct
4	Halted	0 ms	0 KB	-