Submission #293344

#	Time	Username	Problem	Language	Result	Execution time	Memory
293344		AlanChen	Sky Walking (IOI19_walk)	C++14	33 / 100	472 ms	73172 KiB

walk

#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;
template<class A,class B=A> using p=pair<A,B>;
template<class A,class B=less<A>> using pq=priority_queue<A,v<A>,B>;
template<class A> using pqmin=pq<A,greater<A>>;

typedef long long ll;
typedef v<int> vi;
typedef p<int> pi;
typedef string str;

#define f first
#define s second
#define mp make_pair
#define ins insert
#define pb push_back
#define sz(S) (int)S.size()
#define all(S) (S).begin(),(S).end()

#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)

#define trv(x,S) for(auto& x:(S))




#include "walk.h"


const int mx=100100;
int n,m;
int brgs[mx];


v<p<ll,int>> adj[mx*20];//dist,name
void addedge(int a,int b,ll d) {adj[a].pb(mp(d,b)),adj[b].pb(mp(d,a));}


ll dist[mx*20];
pqmin<p<int,int>> to_remove;


pqmin<p<ll,int>> toadd;

long long min_distance(vi x, vi h, vi l, vi r, vi y, int stp, int edp)
{
	n=sz(x);
	l.pb(0),r.pb(0),y.pb(0);
	l.pb(n-1),r.pb(n-1),y.pb(0);
	m=sz(l);
	lp(i,m) brgs[i]=i;
	sort(brgs,brgs+m,[&](int i1,int i2){return l[i1]<l[i2];});

	ll ans=x[edp]-x[stp];

	set<p<ll,int>> cbrg;

	lp(rk,m)
	{
		int i=brgs[rk];
		while(!to_remove.empty()&&to_remove.top().f<l[i]) cbrg.erase(mp(y[to_remove.top().s],to_remove.top().s)),to_remove.pop();

		auto it=cbrg.lower_bound(mp(y[i],0));
		if(it!=cbrg.end()) addedge(it->s,i,it->f-y[i]);
		if(it!=cbrg.begin()) it--,addedge(it->s,i,y[i]-it->f);
		cbrg.ins(mp(y[i],i));
		to_remove.push(mp(r[i],i));
	}





	lp(i,m) dist[i]=-1;
	toadd.push(mp(0,m-2));
	while(!toadd.empty())
	{
		auto top=toadd.top();
		toadd.pop();
		if(top.s==m-1) return ans+top.f;
		if(dist[top.s]==-1)
		{
			dist[top.s]=top.f;
			trv(x,adj[top.s]) if(dist[x.s]==-1) toadd.push(mp(x.f+top.f,x.s));
		}
	}

	return -1;
}


/*

const int mx=100100;
int n,m;
p<ll,pi> brgs[mx];
p<ll,int> blds[mx];


v<p<ll,int>> nodes[mx*20];//dist,name
v<p<ll,int>> adj[mx*20];//dist,name
void addedge(int a,int b,ll d) {adj[a].pb(mp(d,b)),adj[b].pb(mp(d,a));}


ll dist[mx*20];
pqmin<p<ll,int>> toadd;




long long min_distance(vi x, vi h, vi l, vi r, vi y, int stp, int edp)
{
	n=sz(x);
	m=sz(l);



	lp(i,m) brgs[i]={y[i],{l[i],r[i]}};
	sort(brgs,brgs+m,greater<p<ll,pi>>());

	lp(i,n) blds[i]={h[i],i};
	sort(blds,blds+n,greater<pi>());
	map<int,ll> rc;


	nodes[stp].pb(mp(0,0));
	nodes[edp].pb(mp(0,1));

	int nv=2;
	int pidx=0;
	lp(i,m)
	{
		while(pidx<n&&blds[pidx].f>=brgs[i].f) rc[blds[pidx].s]=blds[pidx].f,pidx++;
		auto it=rc.find(brgs[i].s.f);
		for(;it->f!=brgs[i].s.s;it++)
		{
			nodes[it->f].pb(mp(brgs[i].f,nv));
			auto it2=it;it2++;
			addedge(nv,nv+1,x[it2->f]-x[it->f]);
			nv++;
		}
		nodes[it->f].pb(mp(brgs[i].f,nv));
		nv++;
	}
	lp(i,n)
	{
		sort(all(nodes[i]));
		lp(j,1,sz(nodes[i])) if(nodes[i][j].f<=h[i]) addedge(nodes[i][j-1].s,nodes[i][j].s,nodes[i][j].f-nodes[i][j-1].f);
	}


	lp(i,nv) dist[i]=-1;
	toadd.push(mp(0,0));
	while(!toadd.empty())
	{
		auto top=toadd.top();
		toadd.pop();
		if(top.s==1) return top.f;
		if(dist[top.s]==-1)
		{
			dist[top.s]=top.f;
			trv(x,adj[top.s]) if(dist[x.s]==-1) toadd.push(mp(x.f+top.f,x.s));
		}
	}

	return -1;
}

 */

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