Submission #1029184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029184		amirhoseinfar1385	Ancient Books (IOI17_books)	C++17	0 / 100	4 ms	8280 KiB

books

#include"books.h"
#include <vector>
#include<bits/stdc++.h>
const long long maxn=1000000+10;
using namespace std;
long long vis[maxn],visa[maxn],all[maxn],av[maxn],tr[maxn];
long long n;
long long mainres=0,last=0;
vector<pair<long long,pair<long long,long long>>>alle;

struct dsu{
	long long par[maxn];
	dsu(){
		for(long long i=0;i<maxn;i++){
			par[i]=i;
		}
	}
	void clear(){
		for(long long i=0;i<maxn;i++){
			par[i]=i;
		}
	}	
	long long root(long long u){
		if(u==par[u]){
			return u;
		}
		return par[u]=root(par[u]);
	}
	long long con(long long u,long long v){
		u=root(u);
		v=root(v);
		if(u==v){
			return 0;
		}
		par[u]=v;
		return 1;
	}
}ds;

void solve(long long l,long long r,long long cl,long long cr){
	cout<<l<<" "<<r<<" "<<cl<<" "<<cr<<" "<<mainres<<"\n";
	if(l!=cl){
		l--;
		cl=min(cl,av[l]);
		cr=max(cr,tr[av[l]]);
		return solve(l,r,cl,cr);
	}
	if(r!=cr){
		r++;
		cl=min(cl,av[r]);
		cr=max(cr,tr[av[r]]);
		return solve(l,r,cl,cr);
	}
	long long fl=0,fr=0,hl=l-1,hr=r+1,mxl=l,mxr=r;
	for(;;hr++){
		if(hr==n){
			break;
		}
		if(hr==all[hr]){
			continue;
		}
		if(hr>mxr){
			fr+=(hr-mxr)*2;
		}
		mxr=max(mxr,tr[av[hr]]);
		if(av[hr]<l){
			break;
		}
	}
	for(;hl>=0;hl--){
		if(hl==all[hl]){
			continue;
		}
		if(hl<mxl){
			fl+=(mxl-hl)*2;
		}
		mxl=min(mxl,av[hl]);
		if(tr[av[hl]]>r){
			break;
		}
	}
	if(hr==n){
		mainres+=fr+fl;
		return ;
	}
	if(fl<fr){
		mainres+=fl;
		return solve(l,r,mxl,cr);
	}else{
		mainres+=fr;
		return solve(l,r,cl,mxr);
	}
}

long long minimum_walk(std::vector<int> p,int s){
	mainres=0;
	n=p.size();
	for(long long i=0;i<=n;i++){
		vis[i]=visa[i]=0;
		all[i]=p[i];
	}
	last=0;
	long long cnt1=0;
	for(long long i=0;i<n;i++){
		if(p[i]>i){
			cnt1++;
			visa[p[i]]=1;
		}
		if(visa[i]){
			cnt1--;
		}
		mainres+=cnt1*2;
		if(cnt1!=0){
			last=i+1;
		}
	}
	for(long long i=0;i<n;i++){
		if(vis[i]==0){
			//mainres+=2;
			long long now=i;
			do{
				av[now]=i;
				vis[now]=1;
				tr[i]=max(tr[i],now);
				now=p[now];
			}while(now!=i);
		}
	}
	last=-1;
	alle.clear();
	solve(s,s,av[s],tr[av[s]]);
	return mainres;
}

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