oj.uz

Submission #832308

# Submission time Handle Problem Language Result Execution time Memory
832308 2023-08-21T08:44:16 Z Rafi22 Ancient Books (IOI17_books) C++14
0 / 100
 21 ms 41172 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>>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-1].st<=s&&X[u-1].nd>=s)
    		{ 
    			dfs1(u);
    			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;
    	}
    	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)
    		{
    			G[W[i]].pb(Q.back());
    			Q.pop_back();
    		}
    		Q.pb(W[i]);
    	}
    	dfs1(1);
    	
    	return ans;
    }
    /*
    int main()
    {
    	cout<<minimum_walk({3,2,1,0}, 0);
    	return 0;
    }
    */

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41172 KB Output is correct
2 Correct 20 ms 41100 KB Output is correct
3 Correct 20 ms 41080 KB Output is correct
4 Correct 21 ms 41092 KB Output is correct
5 Correct 21 ms 41172 KB Output is correct
6 Incorrect 21 ms 41168 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41172 KB Output is correct
2 Correct 20 ms 41100 KB Output is correct
3 Correct 20 ms 41080 KB Output is correct
4 Correct 21 ms 41092 KB Output is correct
5 Correct 21 ms 41172 KB Output is correct
6 Incorrect 21 ms 41168 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41172 KB Output is correct
2 Correct 20 ms 41100 KB Output is correct
3 Correct 20 ms 41080 KB Output is correct
4 Correct 21 ms 41092 KB Output is correct
5 Correct 21 ms 41172 KB Output is correct
6 Incorrect 21 ms 41168 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 41156 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 41172 KB Output is correct
2 Correct 20 ms 41100 KB Output is correct
3 Correct 20 ms 41080 KB Output is correct
4 Correct 21 ms 41092 KB Output is correct
5 Correct 21 ms 41172 KB Output is correct
6 Incorrect 21 ms 41168 KB 3rd lines differ - on the 1st token, expected: '8', found: '6'
7 Halted 0 ms 0 KB -