Submission #1030573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030573		hirayuu_oj	Ancient Books (IOI17_books)	C++17	100 / 100	312 ms	41396 KiB

books

#include "books.h"
#include<bits/stdc++.h>
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>;
	inline T op(T x,T y){
		return {min(x.first,y.first),max(x.second,y.second)};
	}
	inline 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){
		pos+=size;
		tree[pos]=val;
		pos>>=1;
		while(pos>=1){
			tree[pos]=op(tree[pos*2],tree[pos*2+1]);
			pos>>=1;
		}
	}
	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);
	}
	int sl,sr;
	{
		vector<pair<int,int>> seg=wide;
		sort(all(seg));
		vector<pair<int,int>> re={seg[0]};
		rng(i,1,seg.size()){
			if(seg[i].first<=re.back().second){
				re.back().second=max(re.back().second,seg[i].second);
			}
			else{
				re.emplace_back(seg[i]);
			}
		}
		rep(i,re.size()-1){
			ans+=2*(re[i+1].first-re[i].second);
		}
		for(auto i:re){
			if(i.first<=s&&s<=i.second){
				sl=i.first;
				sr=i.second;
				break;
			}
		}
	}
	vector<int> dist(cnt,INF);
	dist[vis[s]]=0;
	SegTree seg(n);
	rng(i,sl,sr+1){
		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).second;
		if(0<=nxt){
			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).first;
		if(nxt<n){
			if(dist[vis[nxt]]>dis+abs(nxt-ri)){
				dist[vis[nxt]]=dis+abs(nxt-ri);
				pq.push({dist[vis[nxt]],vis[nxt]});
			}
		}
	}
	rep(i,cnt){
		if(wide[i].first==sl){
			ans+=dist[i]*2;
			break;
		}
	}
	return ans;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
      |                                    ^
books.cpp:85:3: note: in expansion of macro 'rng'
   85 |   rng(i,1,seg.size()){
      |   ^~~
books.cpp:4:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define rep(i,n) for(int i=0; i<(n); i++)
      |                                ^
books.cpp:93:3: note: in expansion of macro 'rep'
   93 |   rep(i,re.size()-1){
      |   ^~~
books.cpp:5:36: warning: 'sr' may be used uninitialized in this function [-Wmaybe-uninitialized]
    5 | #define rng(i,l,r) for(int i=(l); i<(r); i++)
      |                                    ^
books.cpp:80:9: note: 'sr' was declared here
   80 |  int sl,sr;
      |         ^~
books.cpp:80:6: warning: 'sl' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |  int sl,sr;
      |      ^~

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