oj.uz

Submission #1029186

# Submission time Handle Problem Language Result Execution time Memory
1029186 2024-07-20T13:36:04 Z amirhoseinfar1385 Ancient Books (IOI17_books) C++17
0 / 100
 3 ms 8284 KB 
#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(i==p[i]){
			av[i]=tr[i]=i;
			continue;
		}
		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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8280 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8280 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8280 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8284 KB secret mismatch
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 8280 KB secret mismatch
2 Halted 0 ms 0 KB -