| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 340027 | 2020-12-26T15:32:32 Z | scales | Mountain Trek Route (IZhO12_route) | C++17 | 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
| # | 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 | 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 |