답안 #971243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971243	2024-04-28T08:31:25 Z	MilosMilutinovic	고대 책들 (IOI17_books)	C++14	100 / 100	339 ms	204144 KB

books

#include "books.h"
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

bool was[1000005];
int n,sl[1000005],sr[1000005],rt[1000005];

namespace rmq{
	int mina[1000005][22],maxa[1000005][22],logs[1000005]; 
	void build(){
		for(int i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
		for(int i=0;i<n;i++){
			mina[i][0]=sl[rt[i]];
			maxa[i][0]=sr[rt[i]];
		}
		for(int j=1;j<22;j++){
			for(int i=0;i+(1<<j)<=n;i++){
				mina[i][j]=min(mina[i][j-1],mina[i+(1<<(j-1))][j-1]);
				maxa[i][j]=max(maxa[i][j-1],maxa[i+(1<<(j-1))][j-1]);
			}
		}
	}
	int qmin(int l,int r){
		int k=logs[r-l+1];
		return min(mina[l][k],mina[r-(1<<k)+1][k]);
	}
	int qmax(int l,int r){
		int k=logs[r-l+1];
		return max(maxa[l][k],maxa[r-(1<<k)+1][k]);
	}
};

void work(int&l,int&r){
	while(true){
		int fl=rmq::qmin(l,r);
		int fr=rmq::qmax(l,r);
		if(fl==l&&fr==r) break;
		l=fl; r=fr;
	}
}

ll minimum_walk(vector<int> p,int s){
	n=(int)p.size();
	ll ans=0;
	for(int i=0;i<n;i++) ans+=abs(p[i]-i);
	for(int i=0;i<n;i++){
		if(was[i]) continue;
		sl[i]=i; sr[i]=i;
		rt[i]=i;
		int x=i;
		while(!was[x]){
			chkmin(sl[i],x);
			chkmax(sr[i],x);
			rt[x]=i;
			was[x]=true;
			x=p[x];
		}
	}
	rmq::build();
	int L=s,R=s;
	for(int i=0;i<n;i++){
		if(p[i]==i) continue;
		chkmin(L,i); chkmax(R,i);
	}
	int cl=s,cr=s;
	while(cl>L||cr<R){
		work(cl,cr);
		int nl=cl,nr=cr;
		int pl=cl,pr=cr;
		ll a=0;
		bool lt=false;
		while(pl>L&&pr==cr){
			a+=2;
			pl--;
			work(pl,pr);
		}
		chkmin(nl,pl);
		chkmax(nr,pr);
		if(pr>cr) lt=true;
		pl=cl; pr=cr;
		ll b=0;
		bool rt=false;
		while(pl==cl&&pr<R){
			b+=2;
			pr++;
			work(pl,pr);
		}
		chkmin(nl,pl);
		chkmax(nr,pr);
		if(pl<cl) rt=true;
		if(lt&&rt) ans+=min(a,b);
		else ans+=a+b;
		cl=nl; cr=nr;
	}
	return ans;
}

Subtask #1
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	1 ms	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	1 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10584 KB	Output is correct
10	Correct	1 ms	10584 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	1 ms	10584 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	1 ms	10588 KB	Output is correct
18	Correct	2 ms	10588 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	1 ms	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	1 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10584 KB	Output is correct
10	Correct	1 ms	10584 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	1 ms	10584 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	1 ms	10588 KB	Output is correct
18	Correct	2 ms	10588 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	10588 KB	Output is correct
22	Correct	1 ms	10588 KB	Output is correct
23	Correct	2 ms	10588 KB	Output is correct
24	Correct	2 ms	10584 KB	Output is correct
25	Correct	2 ms	10588 KB	Output is correct
26	Correct	2 ms	10588 KB	Output is correct
27	Correct	2 ms	10720 KB	Output is correct
28	Correct	2 ms	10588 KB	Output is correct
29	Correct	2 ms	10588 KB	Output is correct

Subtask #3
28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	1 ms	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	1 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10584 KB	Output is correct
10	Correct	1 ms	10584 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	1 ms	10584 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	1 ms	10588 KB	Output is correct
18	Correct	2 ms	10588 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	10588 KB	Output is correct
22	Correct	1 ms	10588 KB	Output is correct
23	Correct	2 ms	10588 KB	Output is correct
24	Correct	2 ms	10584 KB	Output is correct
25	Correct	2 ms	10588 KB	Output is correct
26	Correct	2 ms	10588 KB	Output is correct
27	Correct	2 ms	10720 KB	Output is correct
28	Correct	2 ms	10588 KB	Output is correct
29	Correct	2 ms	10588 KB	Output is correct
30	Correct	325 ms	192044 KB	Output is correct
31	Correct	321 ms	191828 KB	Output is correct
32	Correct	301 ms	196872 KB	Output is correct
33	Correct	326 ms	196948 KB	Output is correct
34	Correct	317 ms	203980 KB	Output is correct
35	Correct	339 ms	203840 KB	Output is correct
36	Correct	332 ms	203636 KB	Output is correct
37	Correct	308 ms	203600 KB	Output is correct
38	Correct	295 ms	204144 KB	Output is correct
39	Correct	314 ms	203660 KB	Output is correct
40	Correct	317 ms	203256 KB	Output is correct
41	Correct	321 ms	203092 KB	Output is correct
42	Correct	317 ms	203140 KB	Output is correct
43	Correct	312 ms	203604 KB	Output is correct

Subtask #4
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10588 KB	Output is correct
2	Correct	1 ms	10712 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	1 ms	10588 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	2 ms	10588 KB	Output is correct
7	Correct	2 ms	10588 KB	Output is correct
8	Correct	2 ms	10588 KB	Output is correct
9	Correct	2 ms	10588 KB	Output is correct
10	Correct	1 ms	10588 KB	Output is correct
11	Correct	2 ms	10588 KB	Output is correct
12	Correct	1 ms	10588 KB	Output is correct
13	Correct	2 ms	10588 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	2 ms	10588 KB	Output is correct
16	Correct	2 ms	10588 KB	Output is correct
17	Correct	2 ms	10708 KB	Output is correct
18	Correct	2 ms	10588 KB	Output is correct
19	Correct	2 ms	10584 KB	Output is correct
20	Correct	2 ms	10584 KB	Output is correct

Subtask #5
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10584 KB	Output is correct
2	Correct	1 ms	10588 KB	Output is correct
3	Correct	2 ms	10588 KB	Output is correct
4	Correct	2 ms	10588 KB	Output is correct
5	Correct	1 ms	10588 KB	Output is correct
6	Correct	1 ms	10588 KB	Output is correct
7	Correct	1 ms	10588 KB	Output is correct
8	Correct	1 ms	10588 KB	Output is correct
9	Correct	1 ms	10584 KB	Output is correct
10	Correct	1 ms	10584 KB	Output is correct
11	Correct	1 ms	10588 KB	Output is correct
12	Correct	2 ms	10588 KB	Output is correct
13	Correct	1 ms	10584 KB	Output is correct
14	Correct	1 ms	10588 KB	Output is correct
15	Correct	1 ms	10588 KB	Output is correct
16	Correct	1 ms	10588 KB	Output is correct
17	Correct	1 ms	10588 KB	Output is correct
18	Correct	2 ms	10588 KB	Output is correct
19	Correct	2 ms	10588 KB	Output is correct
20	Correct	1 ms	10588 KB	Output is correct
21	Correct	2 ms	10588 KB	Output is correct
22	Correct	1 ms	10588 KB	Output is correct
23	Correct	2 ms	10588 KB	Output is correct
24	Correct	2 ms	10584 KB	Output is correct
25	Correct	2 ms	10588 KB	Output is correct
26	Correct	2 ms	10588 KB	Output is correct
27	Correct	2 ms	10720 KB	Output is correct
28	Correct	2 ms	10588 KB	Output is correct
29	Correct	2 ms	10588 KB	Output is correct
30	Correct	325 ms	192044 KB	Output is correct
31	Correct	321 ms	191828 KB	Output is correct
32	Correct	301 ms	196872 KB	Output is correct
33	Correct	326 ms	196948 KB	Output is correct
34	Correct	317 ms	203980 KB	Output is correct
35	Correct	339 ms	203840 KB	Output is correct
36	Correct	332 ms	203636 KB	Output is correct
37	Correct	308 ms	203600 KB	Output is correct
38	Correct	295 ms	204144 KB	Output is correct
39	Correct	314 ms	203660 KB	Output is correct
40	Correct	317 ms	203256 KB	Output is correct
41	Correct	321 ms	203092 KB	Output is correct
42	Correct	317 ms	203140 KB	Output is correct
43	Correct	312 ms	203604 KB	Output is correct
44	Correct	2 ms	10588 KB	Output is correct
45	Correct	1 ms	10712 KB	Output is correct
46	Correct	2 ms	10588 KB	Output is correct
47	Correct	1 ms	10588 KB	Output is correct
48	Correct	1 ms	10588 KB	Output is correct
49	Correct	2 ms	10588 KB	Output is correct
50	Correct	2 ms	10588 KB	Output is correct
51	Correct	2 ms	10588 KB	Output is correct
52	Correct	2 ms	10588 KB	Output is correct
53	Correct	1 ms	10588 KB	Output is correct
54	Correct	2 ms	10588 KB	Output is correct
55	Correct	1 ms	10588 KB	Output is correct
56	Correct	2 ms	10588 KB	Output is correct
57	Correct	1 ms	10588 KB	Output is correct
58	Correct	2 ms	10588 KB	Output is correct
59	Correct	2 ms	10588 KB	Output is correct
60	Correct	2 ms	10708 KB	Output is correct
61	Correct	2 ms	10588 KB	Output is correct
62	Correct	2 ms	10584 KB	Output is correct
63	Correct	2 ms	10584 KB	Output is correct
64	Correct	307 ms	203844 KB	Output is correct
65	Correct	288 ms	203848 KB	Output is correct
66	Correct	312 ms	203940 KB	Output is correct
67	Correct	313 ms	203600 KB	Output is correct
68	Correct	24 ms	32860 KB	Output is correct
69	Correct	22 ms	32860 KB	Output is correct
70	Correct	23 ms	32884 KB	Output is correct
71	Correct	23 ms	32860 KB	Output is correct
72	Correct	23 ms	32860 KB	Output is correct
73	Correct	22 ms	32656 KB	Output is correct
74	Correct	332 ms	203860 KB	Output is correct
75	Correct	323 ms	203716 KB	Output is correct
76	Correct	311 ms	203604 KB	Output is correct
77	Correct	310 ms	203840 KB	Output is correct
78	Correct	323 ms	203788 KB	Output is correct
79	Correct	296 ms	203884 KB	Output is correct
80	Correct	308 ms	203600 KB	Output is correct
81	Correct	307 ms	202892 KB	Output is correct
82	Correct	318 ms	202836 KB	Output is correct
83	Correct	335 ms	203856 KB	Output is correct
84	Correct	338 ms	203704 KB	Output is correct
85	Correct	320 ms	204076 KB	Output is correct
86	Correct	291 ms	203636 KB	Output is correct
87	Correct	323 ms	203600 KB	Output is correct
88	Correct	324 ms	203840 KB	Output is correct
89	Correct	311 ms	203840 KB	Output is correct
90	Correct	309 ms	203604 KB	Output is correct
91	Correct	303 ms	203640 KB	Output is correct
92	Correct	312 ms	202988 KB	Output is correct

답안 #971243

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 10.0 / 10.0

Subtask #3 28.0 / 28.0

Subtask #4 20.0 / 20.0

Subtask #5 30.0 / 30.0

Subtask #1
12.0 / 12.0

Subtask #2
10.0 / 10.0

Subtask #3
28.0 / 28.0

Subtask #4
20.0 / 20.0

Subtask #5
30.0 / 30.0