Submission #283842

#	Time	Username	Problem	Language	Result	Execution time	Memory
283842		balbit	Ancient Books (IOI17_books)	C++14	100 / 100	339 ms	50428 KiB

books

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<" "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template <typename T> void _do(T && x) {cerr<<x<<endl;}
template <typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#endif
const int maxn = 1e6+5;
bool seen[maxn];
int R[maxn], L[maxn];
bool st[maxn];
bool dv[maxn];
int RR[maxn], LL[maxn];

int par[maxn];
int find(int x) {return x == par[x]? x : par[x] = find(par[x]);}
void mrg(int a, int b) {
	a = find(a); b = find(b);
	if (a == b) return;
	RR[a] = max(RR[a], RR[b]);
	LL[a] = min(LL[a], LL[b]);
	par[b] = a;
}
vector<int> here[maxn];
ll minimum_walk(vector<int> p, int s) {
	memset(seen, 0, sizeof seen);
	int n = SZ(p);
	ll re= 0;
	for (int i = 0; i<n; ++i) {
		// --p[i]; 
		re+= abs(i-p[i]);
	}

	// vector<pair<pii,int> > v;

	for (int i = 0; i<n; ++i) {
		if (!seen[i]) {
			st[i] = 1;
			seen[i] = 1;
			R[i] = L[i] = i;
			for (int x = p[i]; x != i; x = p[x]) seen[x] = 1, R[i] = max(R[i], x);
			for (int x = p[i]; x != i; x = p[x]) R[x] = R[i], L[x] = L[i];
			bug(i, L[i], R[i]);
			LL[i] = L[i]; RR[i] =R[i];
		}
	}
	int nmx = 0;
	re -= 2;

	for (int i = 0; i<n; ++i) {
		nmx = max(nmx, R[i]);
		// bug(L[i], R[i]);
		if (nmx <= i) {
			re += 2;
			dv[i] = 1;
		}

		// if (i == s && nmx > i) {
		// 	int ad = 0;
		// 	for (int j = 1; ; ++j) {
		// 		if (p[i+j] != i+j || p[i-j] != i-j) {
		// 			ad = j; break;
		// 		}
		// 	}
		// 	bug(ad);

		// }
	}
	// for (int i = 0; i<n; ++i) par[i] = i;
	// vector<pii> stk;
	// for (int i = 0; i<n; ++i) {
	// 	if (st[i]) {
	// 		while (!stk.empty() && i > stk.back().s) stk.pop_back();
	// 		int newl = i;
	// 		while (!stk.empty() && R[i] > stk.back().s) {
	// 			mrg(i, stk.back().f);
	// 			bug("merged", i, stk.back().f);
	// 			newl = stk.back().f;
	// 			stk.pop_back();
	// 		}
	// 		stk.pb({newl, R[i]});
	// 	}
	// }

	// for (int i = 0; i<n; ++i) {
	// 	if (st[i]) {
	// 		here[find(i)].pb(i);
	// 		for (int x = p[i]; x != i; x = p[x])
	// 			here[find(i)].pb(x), par[x] = find(i);
	// 	}
	// }

	{
		int l= L[s], r = R[s];
		int lat = l, rat = l;

		while (1) {
			if (lat > l) {
				--lat; l = min(l, L[lat]); r = max(r, R[lat]);
			}
			else if (rat < r) {
				++rat; l = min(l, L[rat]); r = max(r, R[rat]);
			}else{
				assert(lat == l && rat ==r);
				int rneed = 0, lneed = 0, rto = r, lto = l;
				for (int i = 1; ; ++i) {
					if (lat-i < 0) {
						goto fofoo;
					}
					if (lat-i < lto) {
						lneed ++; 
					}
					lto = min(lto, L[lat-i]);
					if (R[(lat-i)] > r) {
						bug("HII");
						// assert(L[lat-i] < l);
						// r = R[find(lat-i)]; l = L[find(lat-i)]; 
						break;
					}
				}
				for (int i =1; ; ++i) {
					if (rat+i>=n) {
						goto fofoo;
					}
					if (rat+i > rto) {
						rneed ++; 
					}
					rto = max(rto, R[rat+i]);
					if (L[(rat+i)] < l) {
						bug("HII");
						// assert(R[rat+i] > r);
						r = R[(rat+i)]; l = L[(rat+i)]; break;
					}
				}
				bug(lneed, rneed);
				re += min(lneed, rneed) * 2;
			}
		}

	}
	fofoo:
	for (int i = 0; i<n; ++i) {
		if (p[i] == i && i != s) re -= 2;
		else break;
	}
	for (int i = n-1; i>=0; --i) {
		if (p[i] == i && i != s) re -= 2;
		else break;
	}
	return re;
}

#ifdef BALBIT
signed main(){
	IOS();
	bug(minimum_walk({4,1,2,3,0},1));
	// bug(minimum_walk({3,2,1,0},0));
	// bug(minimum_walk({1,0,3,2},0));
}
#endif

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 20 / 20
• Subtask 5: 30 / 30