제출 #832333

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
832333		Rafi22	고대 책들 (IOI17_books)	C++14	50 / 100	565 ms	91284 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];
    pair<int,int>seg1[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)
    	{
			v/=2;
    		seg[v]=max(seg[2*v],seg[2*v+1]);
    	}
    }
    void del1(int v)
    {
    	v+=pot-1;
    	seg1[v].st=inf;
    	while(v>1)
    	{
			v/=2;
    		seg1[v]=min(seg1[2*v],seg1[2*v+1]);
    	}
    }
     
    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));
    }
    pair<int,int>que1(int v,int a,int b,int l,int r)
    {
    	if(a<=l&&b>=r) return seg1[v];
    	if(r<a||l>b) return {inf,0};
    	return min(que1(2*v,a,b,l,(l+r)/2),que1(2*v+1,a,b,(l+r)/2+1,r));
    }
     
    void dfs(int v)
    {
    	del(V[v].st+1);
    	del1(V[v].nd+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);
    	}
    	while(true)
    	{
    		pair<int,int>p=que1(1,V[v].st+1,V[v].nd+1,1,pot);
    		if(p.st>=V[v].st) break;
    		if(!odw[p.nd]) 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;
    	bool is=0;
    	for(auto u:G[v])
    	{
			//cout<<v<<" "<<u<<" "<<sz(X)<<endl;
    		if(X[u-1].st<=s&&X[u-1].nd>=s)
    		{ 
    			dfs1(u);
    			is=1;
    			cL+=X[u-1].st-X[v-1].st;
    			cR+=X[v-1].nd-X[u-1].nd;
    		}
    		else if(X[u-1].nd<s) cL-=X[u-1].nd-X[u-1].st;
    		else cR-=X[u-1].nd-X[u-1].st;
    		//cout<<v<<" "<<u<<endl;
    		S+=X[u-1].nd-X[u-1].st;
    	}
    	//cout<<v<<" "<<S<<" "<<min(cL,cR)<<endl;
    	if(v==1) ans-=2*S;
    	else if(is) ans+=2*min(cL,cR);
    }
     
    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;
    	for(int i=1;i<=2*pot;i++) seg1[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];
    		}
    		//cout<<l<<" "<<r<<endl;
    		if(l==r&&(l<A||l>B)) continue;
    		seg[l+1+pot-1]={r,c};
    		seg1[r+1+pot-1]={l,c};
    		V.pb({l,r});
    		c++;
    	}
    	for(int i=pot-1;i>0;i--) 
    	{
			seg[i]=max(seg[2*i],seg[2*i+1]);
			if(seg[i].st==inf) cout<<i<<endl;
		}
    	for(int i=pot-1;i>0;i--) seg1[i]=min(seg1[2*i],seg1[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)
    		{
    			G[W[i]].pb(Q.back());
    			Q.pop_back();
    		}
    		Q.pb(W[i]);
    	}
    	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: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30