Submission #379047

#	Time	Username	Problem	Language	Result	Execution time	Memory
379047		autumn_eel	Sky Walking (IOI19_walk)	C++14	0 / 100	117 ms	72168 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<int(n);i++)
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;

const ll INFL=0x3f3f3f3f3f3f3f3f;

struct st{
	int l,r,y;
};

static map<P,int>mp;
static ll d[2000000];
static int cnt=0;
static vector<P>E[2000000];

void add_edge(P a,P b,ll dist){
	if(!mp.count(a)){
		mp[a]=cnt++;
	}
	if(!mp.count(b)){
		mp[b]=cnt++;
	}
	E[mp[a]].push_back(P(dist,mp[b]));
	E[mp[b]].push_back(P(dist,mp[a]));
}


struct Segtree{
	int N;
	vector<ll>dat;
	Segtree(int n){
		N=1;while(N<n)N<<=1;
		dat=vector<ll>(2*N);
	}

	void update(int k,ll x){
		k+=N;
		dat[k]=x;
		while(k>1){
			k>>=1;
			dat[k]=min(dat[k*2],dat[k*2+1]);
		}
	}

	ll query(int l,int r){
		ll res=INFL;
		for(l+=N,r+=N;l<r;l>>=1,r>>=1){
			if(l&1)res=min(res,dat[l++]);
			if(r&1)res=min(res,dat[--r]);
		}
		return res;
	}
};

set<int>vl[200000],vr[200000];

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) {
	int n=x.size();
	int m=l.size();
	
	if(s==0&&g==n-1){
		vector<int>ys{0};
		rep(i,m){
			vl[r[i]].insert(y[i]);
			vr[l[i]].insert(y[i]);
			ys.push_back(y[i]);
		}

		vl[s].insert(0);
		vr[g].insert(0);

		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()),ys.end());
		
		rep(i,n){
			for(int j:vr[i]){
				vl[i].erase(j);
			}
		}

		Segtree seg1(ys.size()),seg2(ys.size());

		rep(i,ys.size()){
			seg1.update(i,INFL);
			seg2.update(i,INFL);
		}
		seg1.update(0,0);
		seg2.update(0,0);

		rep(i,n){
			//~ cout<<"---"<<i<<endl;
			//~ rep(j,ys.size()){
				//~ cout<<seg1.query(j,j+1)<<' ';
			//~ }
			//~ cout<<endl;
			//~ rep(j,ys.size()){
				//~ cout<<seg2.query(j,j+1)<<' ';
			//~ }
			//~ cout<<endl;
			for(int jh:vr[i]){
				//~ cout<<jh<<endl;
				int j=lower_bound(ys.begin(),ys.end(),jh)-ys.begin();
				ll A=seg1.query(0,j+1);
				A=(A>=INFL?INFL:A+jh);
				
				int k=upper_bound(ys.begin(),ys.end(),h[i])-ys.begin();
				ll B=seg2.query(j,k);
				B=(B>=INFL?INFL:B-jh);
				
				ll C=min(A,B);

				if(C==INFL){seg1.update(j,INFL);seg2.update(j,INFL);}
				else{
					seg1.update(j,C-jh);
					seg2.update(j,C+jh);
				}
			}
			for(int jh:vl[i]){
				int j=lower_bound(ys.begin(),ys.end(),jh)-ys.begin();
				seg1.update(j,INFL);
				seg2.update(j,INFL);
			}
		}

		ll ans=x.back()+seg1.query(0,1);
		if(ans>=INFL)return -1;
		return ans;
	}

	return 12345;
	/*
	mp.clear();
	cnt=0;
	rep(i,n)E[i].clear();
	
	vector<st>H;
	rep(i,m){
		H.push_back({l[i],r[i],y[i]});
	}
	sort(H.begin(),H.end(),[](st a,st b){return a.y>b.y;});

	vector<P>V;
	rep(i,n){
		V.push_back(P(h[i],i));
	}
	sort(V.begin(),V.end(),[](P a,P b){return a.first>b.first;});

	set<int>se;
	int cur=0;
	
	for(auto&p:H){
		while(cur<V.size()&&V[cur].first>=p.y){
			se.insert(V[cur].second);
			cur++;
		}
		auto it=se.lower_bound(p.l);
		while(it!=se.end()&&*it<p.r){
			int L=*it;
			it++;
			int R=*it;
			add_edge(P(L,p.y),P(R,p.y),x[R]-x[L]);
		}
	}

	map<int,vector<int>>mp_v;
	mp_v[s].push_back(0);
	mp_v[g].push_back(0);
	
	for(auto&p:mp){
		mp_v[p.first.first].push_back(p.first.second);
	}

	for(auto&v:mp_v){
		rep(i,int(v.second.size())-1){
			add_edge(P(v.first,v.second[i]),P(v.first,v.second[i+1]),v.second[i+1]-v.second[i]);
		}
	}

	if(!mp.count(P(s,0))||!mp.count(P(g,0)))return -1;

	
	priority_queue<P,vector<P>,greater<P>>que;
	memset(d,0x3f,sizeof(d));
	
	d[mp[P(s,0)]]=0;
	que.push(P(0,mp[P(s,0)]));

	while(!que.empty()){
		P p=que.top();que.pop();
		if(d[p.second]!=p.first)continue;

		for(P&u:E[p.second]){
			if(d[u.second]>p.first+u.first){
				d[u.second]=p.first+u.first;
				que.push(P(d[u.second],u.second));
			}
		}
	}

	ll ans=d[mp[P(g,0)]];
	
	if(ans==INFL)return -1;
	return ans;*/
}

Compilation message (stderr)

walk.cpp:15:11: warning: 'd' defined but not used [-Wunused-variable]
   15 | static ll d[2000000];
      |           ^

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