oj.uz

답안 #832333

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832333 2023-08-21T09:12:31 Z Rafi22 고대 책들 (IOI17_books) C++14
50 / 100
 565 ms 91284 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];
    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.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 57556 KB Output is correct
2 Correct 27 ms 57596 KB Output is correct
3 Correct 27 ms 57524 KB Output is correct
4 Correct 27 ms 57524 KB Output is correct
5 Correct 29 ms 57508 KB Output is correct
6 Correct 27 ms 57604 KB Output is correct
7 Correct 28 ms 57572 KB Output is correct
8 Correct 28 ms 57500 KB Output is correct
9 Correct 27 ms 57556 KB Output is correct
10 Correct 27 ms 57580 KB Output is correct
11 Correct 29 ms 57612 KB Output is correct
12 Correct 28 ms 57476 KB Output is correct
13 Correct 28 ms 57520 KB Output is correct
14 Correct 27 ms 57556 KB Output is correct
15 Correct 28 ms 57568 KB Output is correct
16 Correct 28 ms 57508 KB Output is correct
17 Correct 27 ms 57516 KB Output is correct
18 Correct 28 ms 57568 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 57556 KB Output is correct
2 Correct 27 ms 57596 KB Output is correct
3 Correct 27 ms 57524 KB Output is correct
4 Correct 27 ms 57524 KB Output is correct
5 Correct 29 ms 57508 KB Output is correct
6 Correct 27 ms 57604 KB Output is correct
7 Correct 28 ms 57572 KB Output is correct
8 Correct 28 ms 57500 KB Output is correct
9 Correct 27 ms 57556 KB Output is correct
10 Correct 27 ms 57580 KB Output is correct
11 Correct 29 ms 57612 KB Output is correct
12 Correct 28 ms 57476 KB Output is correct
13 Correct 28 ms 57520 KB Output is correct
14 Correct 27 ms 57556 KB Output is correct
15 Correct 28 ms 57568 KB Output is correct
16 Correct 28 ms 57508 KB Output is correct
17 Correct 27 ms 57516 KB Output is correct
18 Correct 28 ms 57568 KB Output is correct
19 Correct 27 ms 57568 KB Output is correct
20 Correct 27 ms 57556 KB Output is correct
21 Correct 27 ms 57524 KB Output is correct
22 Correct 27 ms 57540 KB Output is correct
23 Correct 27 ms 57524 KB Output is correct
24 Correct 28 ms 57524 KB Output is correct
25 Correct 28 ms 57532 KB Output is correct
26 Correct 29 ms 57536 KB Output is correct
27 Correct 27 ms 57520 KB Output is correct
28 Correct 29 ms 57536 KB Output is correct
29 Correct 28 ms 57532 KB Output is correct

Subtask #3
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 57556 KB Output is correct
2 Correct 27 ms 57596 KB Output is correct
3 Correct 27 ms 57524 KB Output is correct
4 Correct 27 ms 57524 KB Output is correct
5 Correct 29 ms 57508 KB Output is correct
6 Correct 27 ms 57604 KB Output is correct
7 Correct 28 ms 57572 KB Output is correct
8 Correct 28 ms 57500 KB Output is correct
9 Correct 27 ms 57556 KB Output is correct
10 Correct 27 ms 57580 KB Output is correct
11 Correct 29 ms 57612 KB Output is correct
12 Correct 28 ms 57476 KB Output is correct
13 Correct 28 ms 57520 KB Output is correct
14 Correct 27 ms 57556 KB Output is correct
15 Correct 28 ms 57568 KB Output is correct
16 Correct 28 ms 57508 KB Output is correct
17 Correct 27 ms 57516 KB Output is correct
18 Correct 28 ms 57568 KB Output is correct
19 Correct 27 ms 57568 KB Output is correct
20 Correct 27 ms 57556 KB Output is correct
21 Correct 27 ms 57524 KB Output is correct
22 Correct 27 ms 57540 KB Output is correct
23 Correct 27 ms 57524 KB Output is correct
24 Correct 28 ms 57524 KB Output is correct
25 Correct 28 ms 57532 KB Output is correct
26 Correct 29 ms 57536 KB Output is correct
27 Correct 27 ms 57520 KB Output is correct
28 Correct 29 ms 57536 KB Output is correct
29 Correct 28 ms 57532 KB Output is correct
30 Correct 128 ms 65332 KB Output is correct
31 Correct 125 ms 65332 KB Output is correct
32 Correct 108 ms 65344 KB Output is correct
33 Correct 494 ms 91284 KB Output is correct
34 Correct 464 ms 91268 KB Output is correct
35 Correct 404 ms 85888 KB Output is correct
36 Correct 281 ms 77296 KB Output is correct
37 Correct 173 ms 70156 KB Output is correct
38 Correct 121 ms 68792 KB Output is correct
39 Correct 118 ms 68428 KB Output is correct
40 Correct 117 ms 66244 KB Output is correct
41 Correct 123 ms 65344 KB Output is correct
42 Correct 124 ms 65624 KB Output is correct
43 Correct 565 ms 89996 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 29 ms 57524 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 27 ms 57556 KB Output is correct
2 Correct 27 ms 57596 KB Output is correct
3 Correct 27 ms 57524 KB Output is correct
4 Correct 27 ms 57524 KB Output is correct
5 Correct 29 ms 57508 KB Output is correct
6 Correct 27 ms 57604 KB Output is correct
7 Correct 28 ms 57572 KB Output is correct
8 Correct 28 ms 57500 KB Output is correct
9 Correct 27 ms 57556 KB Output is correct
10 Correct 27 ms 57580 KB Output is correct
11 Correct 29 ms 57612 KB Output is correct
12 Correct 28 ms 57476 KB Output is correct
13 Correct 28 ms 57520 KB Output is correct
14 Correct 27 ms 57556 KB Output is correct
15 Correct 28 ms 57568 KB Output is correct
16 Correct 28 ms 57508 KB Output is correct
17 Correct 27 ms 57516 KB Output is correct
18 Correct 28 ms 57568 KB Output is correct
19 Correct 27 ms 57568 KB Output is correct
20 Correct 27 ms 57556 KB Output is correct
21 Correct 27 ms 57524 KB Output is correct
22 Correct 27 ms 57540 KB Output is correct
23 Correct 27 ms 57524 KB Output is correct
24 Correct 28 ms 57524 KB Output is correct
25 Correct 28 ms 57532 KB Output is correct
26 Correct 29 ms 57536 KB Output is correct
27 Correct 27 ms 57520 KB Output is correct
28 Correct 29 ms 57536 KB Output is correct
29 Correct 28 ms 57532 KB Output is correct
30 Correct 128 ms 65332 KB Output is correct
31 Correct 125 ms 65332 KB Output is correct
32 Correct 108 ms 65344 KB Output is correct
33 Correct 494 ms 91284 KB Output is correct
34 Correct 464 ms 91268 KB Output is correct
35 Correct 404 ms 85888 KB Output is correct
36 Correct 281 ms 77296 KB Output is correct
37 Correct 173 ms 70156 KB Output is correct
38 Correct 121 ms 68792 KB Output is correct
39 Correct 118 ms 68428 KB Output is correct
40 Correct 117 ms 66244 KB Output is correct
41 Correct 123 ms 65344 KB Output is correct
42 Correct 124 ms 65624 KB Output is correct
43 Correct 565 ms 89996 KB Output is correct
44 Incorrect 29 ms 57524 KB 3rd lines differ - on the 1st token, expected: '3304', found: '3308'
45 Halted 0 ms 0 KB -