# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
340021 | scales | 등산 경로 (IZhO12_route) | C++17 | 1 ms | 364 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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(c[i]==i)
{
x=c[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);
x=fun(x);
}
if(a[x]==a[s])
{
un(x,s);
}
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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |