# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
13377 | dohyun0324 | 등산 경로 (IZhO12_route) | C++98 | 503 ms | 9800 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int,int> ppair;
int len,n,k,a[1000010],pos[1000010];
long long dap,t;
priority_queue<ppair,vector<ppair>,greater<ppair> >q;
int main()
{
int i,p,s1,s2;
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++) scanf("%d",&a[i]);
a[0]=a[n+1]=2147483647;
for(i=1;i<=n;i++)
{
if(a[i]!=a[i-1]) p=i;
if(a[i]!=a[i+1])
{
pos[p]=i; pos[i]=p;
if(a[i+1]>a[i] && a[p-1]>a[p])
{
if(p==1 || i==n) continue;
q.push(make_pair(i-p+1,p));
}
}
}
if(a[n]==a[1])
{
if(a[pos[n]-1]>a[n] && a[n]<a[pos[1]+1]) q.push(make_pair(n-pos[n]+1+pos[1],pos[n]));
pos[pos[n]]=pos[1];
}
else if(a[n]>a[1] && a[1]<a[2]) q.push(make_pair(pos[1],1));
else if(a[n]<a[1] && a[n]<a[n-1]) q.push(make_pair(n-pos[n]+1,pos[n]));
while(1)
{
a[0]=a[n]; a[n+1]=a[1]; pos[0]=pos[n]; pos[n+1]=pos[1];
len=q.top().first; p=q.top().second;
q.pop();
if(s1==s2 || len>=n) break;
if(a[p-1]<a[pos[p]+1])
{
t+=len*(a[p-1]-a[p]);
if(t>=k)
{
t-=len*(a[p-1]-a[p]);
dap+=(k-t)/len;
break;
}
dap+=a[p-1]-a[p];
s1=pos[p-1]; s2=pos[p];
pos[s1]=s2; pos[s2]=s1;
a[s2]=a[p-1];
if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
if(a[s1-1]>a[s2] && a[s2]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
}
else if(a[p-1]>a[pos[p]+1])
{
t+=len*(a[pos[p]+1]-a[p]);
if(t>=k)
{
t-=len*(a[pos[p]+1]-a[p]);
dap+=(k-t)/len;
break;
}
dap+=a[pos[p]+1]-a[p];
s1=p; s2=pos[pos[p]+1];
a[s1]=a[pos[p]+1];
pos[s1]=s2; pos[s2]=s1;
if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
}
else
{
t+=len*(a[pos[p]+1]-a[p]);
if(t>=k)
{
t-=len*(a[pos[p]+1]-a[p]);
dap+=(k-t)/len;
break;
}
dap+=a[pos[p]+1]-a[p];
s1=pos[p-1]; s2=pos[pos[p]+1];
pos[s1]=s2; pos[s2]=s1;
a[s1]=a[pos[p]+1];
if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1<s2) q.push(make_pair(s2-s1+1,s1));
if(a[s1-1]>a[s1] && a[s1]<a[s2+1] && s1>s2) q.push(make_pair(s2+n-s1+1,s1));
}
}
printf("%lld",dap*2);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |