Submission #70896

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
70896	2018-08-23T16:07:39 Z	gnoor	Ancient Books (IOI17_books)	C++17	50 / 100	306 ms	28956 KB

books

#include "books.h"

#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;

bool visit[1000100];

vector<pair<int,int>> uni(vector<pair<int,int>> &tbl) {
	sort(tbl.begin(),tbl.end(),[](const pair<int,int> &a,const pair<int,int> &b) {
			if (a.second!=b.second) return a.second<b.second;
			return a.first<b.first;
			});
	vector<pair<int,int>> re;
	for (int i=0;i<(int)tbl.size();i++) {
		int curl=tbl[i].first;
		while (!re.empty()&&tbl[i].first<=re.back().second) {
			curl=min(curl,re.back().first);
			re.pop_back();
		}
		re.push_back({curl,tbl[i].second});
	}
	return re;
}

vector<pair<pair<int,int>,pair<int,int>>> rem(vector<pair<pair<int,int>,pair<int,int>>> &tbl,vector<pair<int,int>> &out,bool &excess) {
	excess=false;
	sort(tbl.begin(),tbl.end(),[](const pair<pair<int,int>,pair<int,int>> &a,const pair<pair<int,int>,pair<int,int>> &b) {
			if (a.first.second!=b.first.second) return a.first.second<b.first.second;
			return a.first.first>b.first.first;
			});
	
	vector<pair<pair<int,int>,pair<int,int>>> re;
	for (int i=0;i<(int)tbl.size();i++) {
		while (!re.empty()&&tbl[i].first.first<=re.back().first.first) {
			excess=true;
			out.push_back(re.back().first);
			re.pop_back();
		}
		re.push_back(tbl[i]);
	}
	return re;
}

long long minimum_walk(vector<int> p, int s) {
	int n=(int)p.size();
	vector<pair<int,int>> coord;
	vector<pair<int,int>> nonover;
	vector<pair<pair<int,int>,pair<int,int>>> over;
	long long ans=0;

	int globl=-1e9;
	int globr=1e9;

	for (int i=0;i<n;i++) {
		if (visit[i]) continue;
		visit[i]=true;
		int mn=i;
		int mx=i;

		int cl=-1e9;
		int cr=1e9;
		if (i<=s) cl=max(cl,i);
		if (i>=s) cr=min(cr,i);

		int cur=p[i];
		ans+=abs(p[i]-i);
		while (cur!=i) {
			visit[cur]=true;
			mx=max(mx,cur);
			mn=min(mn,cur);

			if (cur<=s) cl=max(cl,cur);
			if (cur>=s) cr=min(cr,cur);

			ans+=abs(p[cur]-cur);
			cur=p[cur];
		}

		if (mn==mx) continue;

		globl=max(globl,cl);
		globr=min(globr,cr);

		coord.push_back({mn,mx});

		if (mn>=s||mx<=s) nonover.push_back({mn,mx});
		else over.push_back({{mn,mx},{cl,cr}});

	}
	coord.push_back({s,s});
	auto re=uni(coord);
	for (int i=1;i<(int)re.size();i++) {
		ans+=(re[i].first-re[i-1].second)*2;
	}

	if (over.empty()) {
		return ans;
	}

	//-------------------------------------------

	bool excess;
	auto over2=rem(over,nonover,excess);

	if (excess) {
		ans+=min(s-globl,globr-s);
	}

	int ll=-1e9;
	int rr=1e9;

	for (auto &i:over2) {
		ll=max(ll,i.second.first);
		rr=min(rr,i.second.second);
	}

	nonover.push_back({ll,ll});
	nonover.push_back({rr,rr});
	nonover.push_back({s,s});

	auto nonover2=uni(nonover);

	long long addr=0;
	bool stflag=false;
	for (int i=0;i<(int)nonover2.size();i++) {
		if (nonover2[i].first<=s&&s<=nonover2[i].second) {
			stflag=true;
			if (nonover2[i].first<=rr&&rr<=nonover2[i].second) break;
			continue;
		}
		if (!stflag) continue;
		addr+=(nonover2[i].first-nonover2[i-1].second)*2;	
		if (nonover2[i].first<=rr&&rr<=nonover2[i].second) break;
	}
	stflag=false;
	long long addl=0;
	for (int i=(int)nonover2.size()-1;i>=0;i--) {
		if (nonover2[i].first<=s&&s<=nonover2[i].second) {
			stflag=true;
			if (nonover2[i].first<=ll&&ll<=nonover2[i].second) break;
			continue;
		}
		if (!stflag) continue;
		addl+=(nonover2[i+1].first-nonover2[i].second)*2;	
		if (nonover2[i].first<=ll&&ll<=nonover2[i].second) break;
	}
	ans+=min(addl,addr);
		
	return ans;
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	488 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	3 ms	568 KB	Output is correct
11	Correct	2 ms	568 KB	Output is correct
12	Correct	3 ms	568 KB	Output is correct
13	Correct	2 ms	568 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	2 ms	628 KB	Output is correct
16	Correct	3 ms	628 KB	Output is correct
17	Correct	3 ms	628 KB	Output is correct
18	Correct	3 ms	628 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	488 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	3 ms	568 KB	Output is correct
11	Correct	2 ms	568 KB	Output is correct
12	Correct	3 ms	568 KB	Output is correct
13	Correct	2 ms	568 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	2 ms	628 KB	Output is correct
16	Correct	3 ms	628 KB	Output is correct
17	Correct	3 ms	628 KB	Output is correct
18	Correct	3 ms	628 KB	Output is correct
19	Correct	3 ms	628 KB	Output is correct
20	Correct	2 ms	628 KB	Output is correct
21	Correct	2 ms	628 KB	Output is correct
22	Correct	3 ms	628 KB	Output is correct
23	Correct	2 ms	628 KB	Output is correct
24	Correct	3 ms	628 KB	Output is correct
25	Correct	2 ms	672 KB	Output is correct
26	Correct	3 ms	672 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	3 ms	704 KB	Output is correct
29	Correct	3 ms	704 KB	Output is correct

Subtask #3

28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	488 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	3 ms	568 KB	Output is correct
11	Correct	2 ms	568 KB	Output is correct
12	Correct	3 ms	568 KB	Output is correct
13	Correct	2 ms	568 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	2 ms	628 KB	Output is correct
16	Correct	3 ms	628 KB	Output is correct
17	Correct	3 ms	628 KB	Output is correct
18	Correct	3 ms	628 KB	Output is correct
19	Correct	3 ms	628 KB	Output is correct
20	Correct	2 ms	628 KB	Output is correct
21	Correct	2 ms	628 KB	Output is correct
22	Correct	3 ms	628 KB	Output is correct
23	Correct	2 ms	628 KB	Output is correct
24	Correct	3 ms	628 KB	Output is correct
25	Correct	2 ms	672 KB	Output is correct
26	Correct	3 ms	672 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	3 ms	704 KB	Output is correct
29	Correct	3 ms	704 KB	Output is correct
30	Correct	305 ms	10928 KB	Output is correct
31	Correct	306 ms	11016 KB	Output is correct
32	Correct	222 ms	11016 KB	Output is correct
33	Correct	221 ms	17612 KB	Output is correct
34	Correct	212 ms	24276 KB	Output is correct
35	Correct	209 ms	28956 KB	Output is correct
36	Correct	179 ms	28956 KB	Output is correct
37	Correct	172 ms	28956 KB	Output is correct
38	Correct	170 ms	28956 KB	Output is correct
39	Correct	167 ms	28956 KB	Output is correct
40	Correct	197 ms	28956 KB	Output is correct
41	Correct	248 ms	28956 KB	Output is correct
42	Correct	235 ms	28956 KB	Output is correct
43	Correct	223 ms	28956 KB	Output is correct

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	28956 KB	Output is correct
2	Correct	2 ms	28956 KB	Output is correct
3	Correct	2 ms	28956 KB	Output is correct
4	Correct	3 ms	28956 KB	Output is correct
5	Correct	3 ms	28956 KB	Output is correct
6	Incorrect	3 ms	28956 KB	3rd lines differ - on the 1st token, expected: '22140', found: '22127'
7	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	4 ms	488 KB	Output is correct
3	Correct	3 ms	544 KB	Output is correct
4	Correct	3 ms	544 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	2 ms	544 KB	Output is correct
10	Correct	3 ms	568 KB	Output is correct
11	Correct	2 ms	568 KB	Output is correct
12	Correct	3 ms	568 KB	Output is correct
13	Correct	2 ms	568 KB	Output is correct
14	Correct	3 ms	628 KB	Output is correct
15	Correct	2 ms	628 KB	Output is correct
16	Correct	3 ms	628 KB	Output is correct
17	Correct	3 ms	628 KB	Output is correct
18	Correct	3 ms	628 KB	Output is correct
19	Correct	3 ms	628 KB	Output is correct
20	Correct	2 ms	628 KB	Output is correct
21	Correct	2 ms	628 KB	Output is correct
22	Correct	3 ms	628 KB	Output is correct
23	Correct	2 ms	628 KB	Output is correct
24	Correct	3 ms	628 KB	Output is correct
25	Correct	2 ms	672 KB	Output is correct
26	Correct	3 ms	672 KB	Output is correct
27	Correct	2 ms	704 KB	Output is correct
28	Correct	3 ms	704 KB	Output is correct
29	Correct	3 ms	704 KB	Output is correct
30	Correct	305 ms	10928 KB	Output is correct
31	Correct	306 ms	11016 KB	Output is correct
32	Correct	222 ms	11016 KB	Output is correct
33	Correct	221 ms	17612 KB	Output is correct
34	Correct	212 ms	24276 KB	Output is correct
35	Correct	209 ms	28956 KB	Output is correct
36	Correct	179 ms	28956 KB	Output is correct
37	Correct	172 ms	28956 KB	Output is correct
38	Correct	170 ms	28956 KB	Output is correct
39	Correct	167 ms	28956 KB	Output is correct
40	Correct	197 ms	28956 KB	Output is correct
41	Correct	248 ms	28956 KB	Output is correct
42	Correct	235 ms	28956 KB	Output is correct
43	Correct	223 ms	28956 KB	Output is correct
44	Correct	3 ms	28956 KB	Output is correct
45	Correct	2 ms	28956 KB	Output is correct
46	Correct	2 ms	28956 KB	Output is correct
47	Correct	3 ms	28956 KB	Output is correct
48	Correct	3 ms	28956 KB	Output is correct
49	Incorrect	3 ms	28956 KB	3rd lines differ - on the 1st token, expected: '22140', found: '22127'
50	Halted	0 ms	0 KB	-