이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "books.h"
#include <iostream>
using namespace std;
const int nmax=1000*1000+5;
int st[nmax],dr[nmax],viz[nmax];
int n,to_l,to_r,l,r,i,x,l1,l2,r1,r2,oldl,oldr,steps_left,steps_right;
long long abss(long long x)
{
if(x<0) return -x;
return x;
}
void ext(int &L,int &R,int oldL,int oldR)
{
int nxtL,nxtR;
while(oldL!=L||oldR!=R)
{
nxtL=L;nxtR=R;
for(int it=oldL-1;it>=L;it--)
{
nxtL=min(nxtL,st[it]);
nxtR=max(nxtR,dr[it]);
}
for(int it=oldR+1;it<=R;it++)
{
nxtL=min(nxtL,st[it]);
nxtR=max(nxtR,dr[it]);
}
oldL=L;oldR=R;
L=nxtL;R=nxtR;
}
}
long long minimum_walk(vector<int> p, int s) {
long long ans=0;
n=p.size();
to_l=s;to_r=s;
for(i=0; i<p.size(); i++)
{
if(p[i]!=i)
{
to_l=min(to_l,i);
to_r=max(to_r,i);
}
ans+=1LL*abss(i-p[i]);
if(!viz[i])
{
st[i]=dr[i]=i;
x=i;
while(!viz[x])
{
st[i]=min(st[i],x);
dr[i]=max(dr[i],x);
viz[x]=1;
x=p[x];
}
x=p[i];
while(x!=i)
{
st[x]=st[i];
dr[x]=dr[i];
x=p[x];
}
}
}
l=s;r=s;
while(l>to_l||r<to_r)
{
l1=l,r1=r;oldl=l;oldr=r;
while(l1>to_l&&r1==r)
{
l1--;steps_left+=2;
ext(l1,r1,oldl,oldr);
oldl=l1;oldr=r1;
}
l2=l,r2=r;oldl=l;oldr=r;
while(r2<to_r&&l2==l)
{
r2++;steps_right+=2;
ext(l2,r2,oldl,oldr);
oldl=l2;oldr=r2;
}
if(r1>r)
{
ans+=1LL*min(steps_left,steps_right);
l=l1;r=r1;
}
else
{
ans+=1LL*steps_left;
ans+=1LL*steps_right;
l=l1;r=r2;
}
}
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0; i<p.size(); i++)
~^~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |