Submission #1071529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071529		LittleOrange	Sky Walking (IOI19_walk)	C++17	10 / 100	1349 ms	154196 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
const ll lim = 1e9;
struct pos{
	ll x,y;
	bool operator<(const pos &o) const{
		return x!=o.x?x<o.x:y<o.y;
	}
	bool operator==(const pos &o) const{
		return x==o.x&&y==o.y;
	}
	bool operator!=(const pos &o) const{
		return x!=o.x||y!=o.y;
	}
};
struct line{
	ll i,v;
	bool operator<(const line &o) const{
		return v>o.v;
	}
};
struct obj{
	ll l,r,y;
	bool operator<(const obj &o) const{
		return l<o.l;
	}
};
struct nod{
	ll l,r,lv,rv;
	nod operator+(const nod &o) const{
		return {l,o.r,min(lv,o.lv+o.l-l),min(rv+o.r-r,o.rv)};
	}
};
struct segtree{
	ll n;
	vector<nod> a;
	vector<ll> xs;
	segtree(const vector<ll> &XS):n(XS.size()),a(XS.size()*4),xs(XS){
		//cerr << "size=" << n << "\n";
		init(1,0,n-1);
	}
	void init(ll i, ll l, ll r){
		if (l==r) a[i] = {xs[l],xs[l],big,big};
		else{
			ll m = l+r>>1;
			init(i<<1,l,m);
			init(i<<1|1,m+1,r);
			a[i] = a[i<<1]+a[i<<1|1];
		}
	}
	void mod(ll i, ll l, ll r, ll x, ll v){
		if (l==r) a[i].lv = a[i].rv = v;
		else{
			ll m = l+r>>1;
			if (x<=m) mod(i<<1,l,m,x,v);
			else mod(i<<1|1,m+1,r,x,v);
			a[i] = a[i<<1]+a[i<<1|1];
		}
	}
	void mod(ll x, ll v){
		ll idx = lower_bound(xs.begin(),xs.end(),x)-xs.begin();
		mod(1,0,n-1,idx,v);
	}
	nod get(ll i, ll l, ll r, ll ql, ll qr){
		if (ql<=l&&r<=qr) return a[i];
		else{
			ll m = l+r>>1;
			if(qr<=m) return get(i<<1,l,m,ql,qr);
			else if(ql>m) return get(i<<1|1,m+1,r,ql,qr);
			else return get(i<<1,l,m,ql,qr)+get(i<<1|1,m+1,r,ql,qr);
		}
	}
	ll qry(ll x){
		ll idx = lower_bound(xs.begin(),xs.end(),x)-xs.begin();
		return min(get(1,0,n-1,0,idx).rv,get(1,0,n-1,idx,n-1).lv);
	}
};
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	ll n = x.size();
	ll m = y.size();
	if (s==0&&g==n-1){
		//cerr << "special fork\n";
		deque<obj> bs;
		for(ll i = 0;i<m;i++){
			bs.push_back({x[l[i]],x[r[i]],y[i]});
		}
		sort(bs.begin(),bs.end());
		//cerr << "cp1\n";
		vector<ll> ys(1,0);
		for(ll i = 0;i<n;i++) ys.push_back(h[i]);
		for(ll i = 0;i<m;i++) ys.push_back(y[i]);
		//cerr << "cp2\n";
		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()),ys.end());
		//cerr << "cp3\n";
		//cerr << ys.size() << "\n";
		segtree t(ys);
		//cerr << "cp4\n";
		t.mod(0,0);
		deque<pair<ll,ll>> exp;
		//cerr << "cp5\n";
		exp.push_back({x[0],0});
		ll ans = big;
		//cerr << "cp6\n";
		for(ll i : x){
			vector<pair<ll,ll>> upd;
			while(bs.size()&&bs.front().l<=i){
				obj o = bs.front();bs.pop_front();
				ll val = t.qry(o.y);
				upd.push_back({o.y,val});
				exp.push_back({o.r,o.y});
			}
			if (i==x.back()){
				ll ans = t.qry(0)+x.back()-x.front();
				if (ans>=big) ans = -1;
				return ans;
			}
			while(exp.size()&&exp.front().first<=i){
				auto o = exp.front();exp.pop_front();
				t.mod(o.second,big);
			}
			for(auto o : upd){
				t.mod(o.first,o.second);
			}
		}
	}
	vector<pos> ps;
	for(ll i = 0;i<n;i++) ps.push_back({x[i],0});
	{
		vector<pair<ll,ll>> builds,bridges;
		for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
		for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
		sort(builds.begin(),builds.end());
		sort(bridges.rbegin(),bridges.rend());
		set<ll> s;
		for(auto [yy,i] : bridges){
			while(builds.size()&&(builds.back().first)>=yy){
				s.insert(builds.back().second);
				////cerr << "add build " << builds.back().second << "\n";
				builds.pop_back();
			}
			for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
				////cerr << "add " << x[*it] << ", " << y[i] << "\n";
				ps.push_back({x[*it],y[i]});
			}
		}
	}
	/*for(ll i = 0;i<m;i++){
		for(ll j = l[i];j<=r[i];j++){
			if (h[j]>=y[i]){
				ps.push_back({x[j],y[i]});
			}
		}
	}*/
	sort(ps.begin(),ps.end());
	ps.erase(unique(ps.begin(),ps.end()),ps.end());
	auto gp = [&](pos p){
		return lower_bound(ps.begin(),ps.end(),p)-ps.begin();
	};
	ll c = ps.size();
	vector<vector<line>> con(c);
	for(ll i = 1;i<c;i++){
		if (ps[i-1].x==ps[i].x){
			ll d = ps[i].y-ps[i-1].y;
			con[i-1].push_back({i,d});
			con[i].push_back({i-1,d});
		}
	}
	{
		vector<pair<ll,ll>> builds,bridges;
		for(ll i = 0;i<n;i++) builds.push_back({h[i],i});
		for(ll i = 0;i<m;i++) bridges.push_back({y[i],i});
		sort(builds.begin(),builds.end());
		sort(bridges.rbegin(),bridges.rend());
		set<ll> s;
		for(auto [yy,i] : bridges){
			vector<ll> v;
			while(builds.size()&&(builds.back().first)>=yy){
				s.insert(builds.back().second);
				////cerr << "add build " << builds.back().second << "\n";
				builds.pop_back();
			}
			for(auto it = s.lower_bound(l[i]);it!=s.end()&&(*it)<=r[i];it++){
				////cerr << "add " << x[*it] << ", " << y[i] << "\n";
				v.push_back(gp({x[*it],y[i]}));
			}
			for(ll j = 1;j<v.size();j++){
				ll d = ps[v[j]].x-ps[v[j-1]].x;
				con[v[j-1]].push_back({v[j],d});
				con[v[j]].push_back({v[j-1],d});
			}
		}
	}
	/*for(ll i = 0;i<m;i++){
		vector<ll> v;
		for(ll j = l[i];j<=r[i];j++){
			if (h[j]>=y[i]){
				v.push_back(gp({x[j],y[i]}));
			}
		}
		for(ll j = 1;j<v.size();j++){
			ll d = ps[v[j]].x-ps[v[j-1]].x;
			con[v[j-1]].push_back({v[j],d});
			con[v[j]].push_back({v[j-1],d});
		}
	}*/
	ll start = gp({x[s],0});
	ll goal = gp({x[g],0});
	vector<ll> dis(c,big);
	priority_queue<line> q;
	q.push({start,0});
	while(q.size()){
		auto [i,v] = q.top();q.pop();
		if(dis[i]<=v) continue;
		dis[i] = v;
		for(auto [j,w] : con[i]){
			q.push({j,v+w});
		}
	}
	ll ans = dis[goal];
	if (ans>=big) ans = -1;
	return ans;
}

Compilation message (stderr)

walk.cpp: In member function 'void segtree::init(ll, ll, ll)':
walk.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |    ll m = l+r>>1;
      |           ~^~
walk.cpp: In member function 'void segtree::mod(ll, ll, ll, ll, ll)':
walk.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |    ll m = l+r>>1;
      |           ~^~
walk.cpp: In member function 'nod segtree::get(ll, ll, ll, ll, ll)':
walk.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |    ll m = l+r>>1;
      |           ~^~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:106:6: warning: unused variable 'ans' [-Wunused-variable]
  106 |   ll ans = big;
      |      ^~~
walk.cpp:190:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |    for(ll j = 1;j<v.size();j++){
      |                 ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43