Submission #1030457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030457		vjudge1	Ancient Books (IOI17_books)	C++17	12 / 100	1 ms	432 KiB

books

#include "books.h"
#include<bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rng(i,l,r) for(int i=(l); i<(r); i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const int INF=INT_MAX>>1;

struct SegTree{

	using T=pair<int,int>;
	T op(T x,T y){
		return {min(x.first,y.first),max(x.second,y.second)};
	}
	T e(){
		return {INF,-INF};
	}

	vector<T> tree;
	int size;
	SegTree(int sz):size(sz){
		tree.resize(size*2,e());
	}
	inline T get(int pos){
		return tree[pos+size];
	}
	inline void set(int pos,T val){
		tree[pos+size]=val;
	}
	T prod(int lf,int ri){
		lf+=size;
		ri+=size;
		T rl=e();
		T rr=e();
		while(lf<ri){
			if(lf&1){
				rl=op(rl,tree[lf]);
				lf++;
			}
			if(ri&1){
				ri--;
				rr=op(tree[ri],rr);
			}
			lf>>=1;
			ri>>=1;
		}
		return op(rl,rr);
	}
};

long long minimum_walk(std::vector<int> p, int s) {
	int n=p.size();
	vector<int> vis(n,-1);
	vector<pair<int,int>> wide;
	int cnt=0;
	ll ans=0;
	rep(i,n){
		if(vis[i]>=0)continue;
		if(p[i]==i&&i!=s)continue;
		int lf=i;
		int ri=i;
		int pos=i;
		while(vis[p[pos]]==-1){
			ans+=abs(pos-p[pos]);
			pos=p[pos];
			vis[pos]=cnt;
			lf=min(lf,pos);
			ri=max(ri,pos);
		}
		cnt++;
		wide.emplace_back(lf,ri);
	}
	vector<int> dist(cnt,INF);
	dist[vis[s]]=0;
	SegTree seg(n);
	rep(i,n){
		if(vis[i]!=-1)seg.set(i,{i,i});
	}
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
	pq.push({0,vis[s]});
	while(!pq.empty()){
		int dis,pos;
		tie(dis,pos)=pq.top();
		pq.pop();
		if(dist[pos]!=dis)continue;
		int lf,ri;
		tie(lf,ri)=wide[pos];
		while(true){
			int nxt=seg.prod(lf+1,ri).first;
			if(nxt>n)break;
			seg.set(nxt,seg.e());
			if(dist[vis[nxt]]>dis){
				dist[vis[nxt]]=dis;
				pq.push({dist[vis[nxt]],vis[nxt]});
			}
		}
		int nxt;
		nxt=seg.prod(0,lf).first;
		if(nxt<n){
			if(dist[vis[nxt]]>dis+abs(nxt-lf)){
				dist[vis[nxt]]=dis+abs(nxt-lf);
				pq.push({dist[vis[nxt]],vis[nxt]});
			}
		}
		nxt=seg.prod(ri+1,n).second;
		if(nxt>=0){
			if(dist[vis[nxt]]>dis+abs(nxt-ri)){
				dist[vis[nxt]]=dis+abs(nxt-ri);
				pq.push({dist[vis[nxt]],vis[nxt]});
			}
		}
	}
	for(ll i:dist)ans+=i*2;
	return ans;
}

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