oj.uz

답안 #832307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832307 2023-08-21T08:43:01 Z Rafi22 고대 책들 (IOI17_books) C++14
0 / 100
 26 ms 41180 KB 
#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;
		if(!odw[p.nd]) dfs(p.nd);
	}
}
vector<pair<int,int>>XX;
int W[N];
vector<int>G[N];
int s,n;
ll ans=0;

void dfs1(int v)
{
	//cout<<v<<endl;
	//cout<<v<<endl;
	int cL=0,cR=0,S=0;
	for(auto u:G[v])
	{
		//cout<<v<<" "<<u<<endl;
		if(XX[u-1].st<=s&&XX[u-1].nd>=s)
		{ 
			dfs1(u);
			cL=XX[u-1].st-XX[v-1].st;
			cR=XX[v-1].nd-XX[u-1].nd;
		}
		else if(XX[u-1].nd<s) cL-=XX[u-1].nd-XX[u-1].st;
		else cR-=XX[u-1].nd-XX[u-1].st;
		//cout<<v<<" "<<u<<endl;
		S+=XX[u-1].nd-XX[u-1].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;
	XX.pb({-1,n});
	W[n]=1;
	for(int i=0;i<c;i++)
	{
		if(odw[i]) continue;
		L=inf,R=-inf;
		dfs(i);
		XX.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&&XX[Q.back()-1].st>XX[W[i]-1].st)
		{
			G[W[i]].pb(Q.back());
			Q.pop_back();
		}
		Q.pb(W[i]);
	}
	//cout<<sz(XX)<<endl;
	dfs1(1);
	
	return ans;
}
/*
int main()
{
	int nn,s;
	cin>>nn>>s;
	vector<int>V(nn);
	for(int i=0;i<nn;i++) V[i]=i;
	random_shuffle(all(V));
	for(int i=0;i<nn;i++) cout<<V[i]<<" ";
	cout<<endl;
	cout<<minimum_walk(V,s);
	return 0;
}*/

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 41112 KB Output is correct
2 Correct 17 ms 41180 KB Output is correct
3 Correct 22 ms 41160 KB Output is correct
4 Correct 19 ms 41172 KB Output is correct
5 Correct 26 ms 41136 KB Output is correct
6 Incorrect 24 ms 41124 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 41112 KB Output is correct
2 Correct 17 ms 41180 KB Output is correct
3 Correct 22 ms 41160 KB Output is correct
4 Correct 19 ms 41172 KB Output is correct
5 Correct 26 ms 41136 KB Output is correct
6 Incorrect 24 ms 41124 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 41112 KB Output is correct
2 Correct 17 ms 41180 KB Output is correct
3 Correct 22 ms 41160 KB Output is correct
4 Correct 19 ms 41172 KB Output is correct
5 Correct 26 ms 41136 KB Output is correct
6 Incorrect 24 ms 41124 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 20 ms 41172 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 41112 KB Output is correct
2 Correct 17 ms 41180 KB Output is correct
3 Correct 22 ms 41160 KB Output is correct
4 Correct 19 ms 41172 KB Output is correct
5 Correct 26 ms 41136 KB Output is correct
6 Incorrect 24 ms 41124 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -