제출 #831818

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831818		Rafi22	고대 책들 (IOI17_books)	C++14	0 / 100	19 ms	41172 KiB

books

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=1000007,pot=1<<20;

bool odw[N];
pair<int,int>seg[2*pot+7];

int L,R;
vector<pair<int,int>>V;

void del(int v)
{
	v+=pot-1;
	seg[v].st=-inf;
	while(v>1)
	{
		seg[v]=max(seg[2*v],seg[2*v+1]);
		v/=2;
	}
}

pair<int,int>que(int v,int a,int b,int l,int r)
{
	if(a<=l&&b>=r) return seg[v];
	if(r<a||l>b) return {-inf,0};
	return max(que(2*v,a,b,l,(l+r)/2),que(2*v+1,a,b,(l+r)/2+1,r));
}

void dfs(int v)
{
	del(V[v].st+1);
	odw[v]=1;
	L=min(L,V[v].st);
	R=max(R,V[v].nd);
	while(true)
	{
		pair<int,int>p=que(1,V[v].st+1,V[v].nd+1,1,pot);
		if(p.st<=V[v].nd) break;
		dfs(p.nd);
	}
}
vector<pair<int,int>>X;
int W[N];
vector<int>G[N];
int s,n;
ll ans=0;

void dfs1(int v)
{
	cout<<v<<endl;
	int cL=0,cR=0,S=0;
	for(auto u:G[v])
	{
		if(X[u].st<=s&&X[u].nd>=s)
		{ 
			dfs(u);
			cL=X[u].st-X[v].st;
			cR=X[v].nd-X[u].nd;
		}
		else if(X[u].nd<s) cL-=X[u].nd-X[u].st;
		else cR-=X[u].nd-X[u].st;
		S+=X[u].nd-X[u].st;
	}
	if(v!=1) ans+=2*min(cL,cR);
	else ans-=2*S;
}

ll minimum_walk(vector<int>p,int ss)
{
	s=ss;
	n=sz(p);
	for(int i=0;i<n;i++) ans+=abs(i-p[i]);
	for(int i=1;i<=2*pot;i++) seg[i].st=-inf;
	int c=0;
	int A=0,B=n-1;
	while(A<s&&p[A]==A) A++;
	while(s<B&&p[B]==B) B--;
	ans+=2*(B-A);
	for(int i=0;i<n;i++)
	{
		if(odw[i]) continue;
		int l=inf,r=-inf,x=i;
		while(!odw[x])
		{
			odw[x]=1;
			l=min(l,x);
			r=max(r,x);
			x=p[x];
		}
		if(l==r&&(l<A||l>B)) continue;
		seg[l+1+pot-1]={r,c};
		V.pb({l,r});
		c++;
	}
	for(int i=pot-1;i>0;i--) seg[i]=max(seg[2*i],seg[2*i+1]);
	memset(odw,0,sizeof odw);
	
	int it=2;
	X.pb({-1,n});
	W[n]=1;
	for(int i=0;i<c;i++)
	{
		if(odw[i]) continue;
		L=inf,R=-inf;
		dfs(i);
		X.pb({L,R});
		W[R]=it;
		it++;
	}
	vector<int>Q;
	for(int i=0;i<=n;i++)
	{
		if(W[i]==0) continue;
		while(sz(Q)>0&&X[Q.back()-1].st>X[W[i]-1].st)
		{
			//cout<<W[i]<<" "<<Q.back()<<endl;
			G[W[i]].pb(Q.back());
			Q.pop_back();
		}
		Q.pb(W[i]);
	}
	dfs1(1);
	
	return ans;
}
/*
int main()
{
	cout<<minimum_walk({0, 2, 3, 1}, 0);
	return 0;
}*/

• Subtask 1: 0 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30