Submission #1326423

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326423		thelegendary08	Ancient Books (IOI17_books)	C++17	50 / 100	2094 ms	147220 KiB

books

#include "books.h"
#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vvi vector<vi>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<endl;
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
using namespace std;
inline pii mrg(pii a, pii b){return mp(min(a.F,b.F),max(a.S,b.S));}
struct segtree{
	int n; vpii tree; 
	segtree(vpii &v){
		n=v.size(); tree.resize(n*2+5); for(int i = n; i < 2 * n; i++)tree[i]=v[i-n]; for(int i = n-1; i >= 1; i--)tree[i]=mrg(tree[i*2],tree[i*2+1]);
	}
	pii quer(int l, int r){
		pii ret = mp(1e9,-1e9); l+=n;r+=n; while(l<=r){
			if(l%2)ret=mrg(ret,tree[l++]); if(r%2==0)ret=mrg(ret,tree[r--]); l/=2;r/=2;
		} return ret;
	}
};
struct seg{
	int n; vi mn, mx; 
	seg(vi &a, vi &b){
		n=a.size(); mn.resize(4*n+5); mx.resize(4*n+5); buildmn(1,0,n-1,a); buildmx(1,0,n-1,b);
	}
	void pull(int v){
		mn[v]=min(mn[v*2],mn[v*2+1]); mx[v]=max(mx[v*2],mx[v*2+1]);
	}
	void buildmn(int v, int l, int r, vi &a){
		if(l==r){mn[v]=a[l]; return;} int mid = l + r >> 1; buildmn(v*2,l,mid,a); buildmn(v*2+1,mid+1,r,a); pull(v);
	}
	void buildmx(int v, int l, int r, vi &a){
		if(l==r){mx[v]=a[l]; return;} int mid = l + r >> 1; buildmx(v*2,l,mid,a); buildmx(v*2+1,mid+1,r,a); pull(v);
	}
	int last_larger(int v, int tl, int tr, int l, int r, int x){
		if(mx[v] < x)return -1; if(tl > r || tr < l)return -1; if(tl==tr)return x; 
		int tm = tl + tr >> 1; int lef = last_larger(v*2+1,tm+1,tr,l,r,x); if(lef!=-1)return lef; 
		return last_larger(v*2,tl,tm,l,r,x); 
	}
	int first_less(int v, int tl, int tr, int l, int r, int x){
		if(mn[v] > x)return -1; if(tl > r || tr < l)return -1; if(tl==tr)return x; 
		int tm = tl + tr >> 1; int lef = first_less(v*2,tl,tm,l,r,x); if(lef!=-1)return lef; 
		return first_less(v*2+1,tm+1,tr,l,r,x);
	}
};
long long minimum_walk(std::vector<signed> p, signed s) {
	int n = p.size(), ans = 0; f0r(i,n)ans+=abs(p[i]-i); vector<bool>vis(n); vector<pair<int,int>>r(n); f0r(i,n)if(!vis[i]){
		int cur = i; vi v; int mn = 1e9, mx = -1e9; while(!vis[cur]){vis[cur] = 1; v.pb(cur); mn=min(mn,cur),mx=max(mx,cur); cur = p[cur];}
		for(auto u : v)r[u]=mp(mn,mx);
	} segtree S = segtree(r); //for(auto u : r)cout<<u.first<<' '<<u.second<<'\n'; S.quer(0,0);
	int a = 1e9, b = -1e9;  f0r(i,n)if(p[i]!=i)a=min(a,i),b=max(b,i); if(a==1e9)return ans;
	vi ls, rs; f0r(i,n)ls.pb(r[i].F),rs.pb(r[i].S); seg T = seg(ls,rs); int L = s, R = s; 
	vi dif(n); f0r(i,n){int a = i, b = p[i]; if(a>b)swap(a,b); dif[a]++; dif[b]--;}
	while(1){
		while(1){
			auto [l_, r_] = S.quer(L,R); if(l_==L&&r_==R)break; L=l_, R=r_; 
		}
		int cl = T.last_larger(1,0,n-1,0,L-1,s); if(cl==-1){
			if(L>a){
				L--; ans+=2; int cur = 0; while(L>a){
					cur -= dif[L]; if(cur==0)ans+=2; L--; 
				}
			}
			if(R<b){
				R++; ans+=2; int cur = 0; while(R<b){
					cur += dif[R]; if(cur==0)ans+=2; R++; 
				}
			}
			break;
		}
		int cur = 0, lcost = 1; for(int i = L-1; i >= cl + 1; i--){
			cur -= dif[i]; if(cur==0)lcost++;  
		} 
		int cr = T.first_less(1,0,n-1,R+1,n-1,s); cur = 0; int rcost = 1; for(int i = R+1; i<cr; i++){
			cur += dif[i]; if(cur==0)rcost++; 
		}
		ans += min(lcost, rcost) * 2; L = cl, R = cr; 
	} return ans; 
	/*
	vvi dp(n, vi(n,1e9)); dp[s][s]=0; deque<pii>q; q.push_front(mp(s,s)); while(!q.empty()){
		int x = q.front().F, y = q.front().S; q.pop_front(); 
		auto [x_, y_] = S.quer(x,y); if(dp[x_][y_]==1e9){
			dp[x_][y_] = dp[x][y]; q.push_front(mp(x_,y_));
		}
		if(y+1 < n && dp[x][y+1]==1e9)dp[x][y+1]=dp[x][y]+1,q.pb(mp(x,y+1));
		if(x-1 >= 0 && dp[x-1][y]==1e9)dp[x-1][y]=dp[x][y]+1,q.pb(mp(x-1,y));
	} int mn = 1e9; f0r(i,n)FOR(j,i,n)if(i<=a&&j>=b)mn=min(mn,dp[i][j]);
	return ans+mn*2;
	*/
	/*
	vi dif(n); f0r(i,n){int a = i, b = p[i]; if(a>b)swap(a,b); dif[a]++; dif[b]--;}
	int cur = 0; vi w(n-1); int lst = -1; f0r(i,n-1){cur+=dif[i]; if(cur)w[i]=1,lst=i;} 
	for(int i = lst; i >= 0; i--)if(w[i]==0)ans+=2; return ans;
	*/
}

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