Submission #826509

#	Time	Username	Problem	Language	Result	Execution time	Memory
826509		I_Love_EliskaM_	Sky Walking (IOI19_walk)	C++17	57 / 100	1450 ms	233912 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
using ll = long long;
const ll inf = 1e18;
#define pi pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()

#define int ll
const int sz=1<<30;
struct sgt {
	sgt *L, *R; int s;
	sgt() {
		L=R=NULL; s=inf;
	}
	void set(int l, int r, int i, int x) {
		if (r-l==1) {
			s=x; return;
		}
		int m=(l+r)>>1;
		if (i<m) {
			if (!L) L=new sgt();
			L->set(l,m,i,x);
		} else {
			if (!R) R=new sgt();
			R->set(m,r,i,x);
		}
		s = min(L?L->s:inf, R?R->s:inf);
	}
	void set(int i, int x) {
		set(0,sz,i,x);
	}
	int query(int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return inf;
		if (lx<=l && r<=rx) return s;
		int m=(l+r)>>1;
		int lq=L?L->query(l,m,lx,rx):inf;
		int rq=R?R->query(m,r,lx,rx):inf;
		return min(lq,rq);
	}
	int query(int l, int r) {
		return query(0,sz,l,r);
	}
};

const int N=1e5+55;
vector<pi> adj[10*N];
ll d[10*N];

map<int,int> c[N]; int _z=0; const int Z=1e9+5;
int ind(int x, int y) {
	if (c[x].count(y)) return c[x][y];
	return c[x][y]=_z++;
}
#undef int

ll p12(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
	int n=x.size(), m=l.size();
	
	vector<vector<int>> g1(n);
	vector<vector<int>> g2(m);
	g1[s].pb(0);
	g1[g].pb(0);

	vector<pi> v;
	forn(i,n) v.pb({h[i],i});
	forn(i,m) v.pb({y[i],-i-1});
	sort(rall(v));

	set<int> st; 
	for(auto&z:v) {
		int y=z.f, i=z.s;
		if (i>=0) {
			st.insert(i); continue;
		}
		i*=-1; --i;
		auto it=st.upper_bound(l[i]);
		vector<int> v;
		while (1) {
			int j=*it;
			v.pb(j);
			if (j==r[i]) break;
			++it;
		}
		if (v.size() > 10 && max(n,m)>50) return -2;
		g1[l[i]].pb(y);
		int last=l[i];
		for(auto&j:v) {
			adj[ind(last,y)].pb({ind(j,y),x[j]-x[last]});
			adj[ind(j,y)].pb({ind(last,y),x[j]-x[last]});
			g1[j].pb(y);
			last=j;
		}
	}

	forn(i,n) {
		sort(all(g1[i]));
		int sz=g1[i].size();
		forn(j,sz-1) {
			adj[ind(i,g1[i][j])].pb({ind(i,g1[i][j+1]),g1[i][j+1]-g1[i][j]});
			adj[ind(i,g1[i][j+1])].pb({ind(i,g1[i][j]),g1[i][j+1]-g1[i][j]});
		}
	}

	forn(i,_z) d[i]=inf;
	priority_queue<pair<ll,ll>> q; q.push({0,ind(s,0)});

	while(q.size()) {
		auto it=q.top(); q.pop();
		ll di=-it.f, u=it.s;
		if (d[u]<=di) continue;
		d[u]=di;
		for(auto&e:adj[u]) {
			int v=e.f, w=e.s;
			if (d[v]!=inf) continue;
			q.push({-di-w,v});
		}
	}

	if (d[ind(g,0)]==inf) return -1;
	return d[ind(g,0)];
}

ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
	int n=x.size(), m=l.size();

    if (s!=0 || g!=n-1) return p12(x,h,l,r,y,s,g);
	
	#define int ll

	sgt bottom, top;
	bottom.set(0,0);
	top.set(0,0);
	vector<vector<int>> add(n), del(n);
	del[0].pb(0);
	add[n-1].pb(0);
	forn(i,m) {
		add[l[i]].pb(y[i]);
		del[r[i]].pb(y[i]);
	}
	forn(i,n) {
		vector<pi> toset;
		for(auto&y:add[i]) {
			int f = bottom.query(0,y+1);
			int s = top.query(y,sz);
			if (min(f,s)==inf) return -1;
			f+=y; s-=y;
			int x=min(f,s);
			toset.pb({y,x});
		}
		for(auto&y:del[i]) {
			bottom.set(y,inf);
			top.set(y,inf);
		}
		for(auto&x:toset) {
			bottom.set(x.f,x.s-x.f);
			top.set(x.f,x.s+x.f);
		}
	}
	int f = top.s+x[n-1]-x[0];
	return f;

	#undef int
}

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