Submission #1067541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067541		jamjanek	Sky Walking (IOI19_walk)	C++17	100 / 100	1081 ms	144540 KiB

walk

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

vector<int>l,r,y,x,h;

const int base = 1<<17;

int drzewo[2*base];

int wiekszeL(int x, int val){
	x+=base;
	while(drzewo[x]<val && x&(x-1)){
		if(x%2==1)x/=2;
		else x--;
	}
	if(drzewo[x]>=val){
		while(x<base)
			if(drzewo[x*2+1]>=val)
				x=x*2+1;
			else
				x=x*2;
		return x-base;
	}
	else
		return -1;
}
int wiekszeR(int x, int val){
	x+=base;
	while(drzewo[x]<val && x&(x+1)){
		if(x%2==0)x/=2;
		else x++;
	}
	if(drzewo[x]>=val){
		while(x<base)
			if(drzewo[x*2]>=val)
				x=x*2;
			else
				x=x*2+1;
		return x-base;
	}
	else
		return base;
}


int tree[2*base];
void ustaw(int w, int l, int p, int a, int b, int v){
	if(a<=l && p<=b){
		tree[w] = v;
		return;
	}
	if(b<l || p<a)return;
	if(tree[w]!=-1)
		tree[w*2] = tree[w*2+1] = tree[w];
	ustaw(w*2, l, (l+p)/2, a, b, v);
	ustaw(w*2+1, (l+p)/2+1, p, a, b, v);
	tree[w] = -1;
}
int odczyt(int w){
	int res = -1;
	w+=base;
	while(w>0){
		if(tree[w]!=-1)
			res = tree[w];
		w/=2;
	}
	return res;
}

void dodaj(int a, int b, int h){
	l.push_back(a);
	r.push_back(b);
	y.push_back(h);
}
vector<pair<int,long long>>graf[700010];
long long dist[700010];
bool odw[700010];
map<pair<int,int>,int>mapa;
long long odl(pair<int,int>a, pair<int,int>b){
	return abs(a.second-b.second);
}
long long odl1(pair<int,int>a, pair<int,int>b){
	return abs(x[a.first]-x[b.first]);
}
map<int,vector<pair<int,int>>>poziomy;
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int s, int g) {
	x = X;
	h = H;
	// podzielic kazda pozioma
	// dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy
	vector<tuple<int,int,int,int>>przedzialy;
	int n = x.size();
	int m = L.size();
	int i;
	for(i=0;i<n;i++)
		drzewo[i+base]=h[i];
	for(i=base-1;i>0;i--)
		drzewo[i]=max(drzewo[i*2], drzewo[i*2+1]);
	if(s>g)swap(s,g);
	for(i=0;i<m;i++){
		poziomy[Y[i]].push_back({L[i],R[i]});
		if(L[i]<s && R[i]>g){
			dodaj(L[i],s,Y[i]);
			dodaj(s,g,Y[i]);
			dodaj(g,R[i],Y[i]);
		}
		else if(L[i]<s && R[i]>s){
			dodaj(L[i],s,Y[i]);
			dodaj(s,R[i],Y[i]);
		}
		else if(g<R[i] && L[i]<g){
			dodaj(L[i],g,Y[i]);
			dodaj(g,R[i],Y[i]);
		}
		else{
			dodaj(L[i],R[i],Y[i]);
		}
	}
	m = l.size();
	for(i=0;i<m;i++)
		przedzialy.push_back({y[i],l[i],r[i],0});
	sort(przedzialy.begin(), przedzialy.end());
	for(i=0;i<m;i++)
		get<3>(przedzialy[i]) = i;
	for(i=0;i<n;i++)tree[i+base] = -1;
	for(i=base-1;i>0;i--)
		tree[i] = -1;
	ustaw(1, 0,base-1,s,s,0);
	ustaw(1, 0,base-1,g,g,0);
	mapa[{s,0}]=0;
	mapa[{g,0}]=1;
	for(auto j: przedzialy){
		auto [Y,L,R,i] = j;
		int a = wiekszeR(L, Y);
		if(a<=R){
			int b = odczyt(a);
			if(b!=-1 && mapa.find({a, b})==mapa.end())
				mapa[{a,b}] = mapa.size();
			if(mapa.find({a, Y})==mapa.end())
				mapa[{a,Y}] = mapa.size();
		}
		a = wiekszeL(R,Y);
		if(a>=L){
			int b = odczyt(a);
			if(b!=-1 &&mapa.find({a, b})==mapa.end())
				mapa[{a,b}] = mapa.size();
			if(mapa.find({a, Y})==mapa.end())
				mapa[{a,Y}] = mapa.size();
		}
		ustaw(1, 0, base-1, L, R, Y);
	}
	vector<pair<pair<int,int>,int>>wartosci;
	for(auto j=mapa.begin();j!=mapa.end();j++){
		auto xd = *j;
		wartosci.push_back({xd.first, xd.second});
		auto next = j;
		next++;
		if(next==mapa.end())break;
		if((*next).first.first==(*j).first.first){
			graf[(*next).second].push_back({(*j).second, odl((*j).first, (*next).first)});
			graf[(*j).second].push_back({(*next).second, odl((*j).first, (*next).first)});
		}
	}

	for(auto &j: poziomy){
		auto &vec = j.second;
		vector<pair<int,int>>dobre;
		sort(vec.begin(), vec.end());
		int koniec = (*vec.begin()).second, pocz = (*vec.begin()).first;
		for(auto k: vec){
			if(k.first<=koniec)
				koniec = max(k.second, koniec);
			else{
				dobre.push_back({pocz, koniec});
				pocz = k.first;
				koniec = k.second;
			}
		}
		dobre.push_back({pocz,koniec});
		vec = dobre;
	}
		
	mapa.clear();
	for(auto j:wartosci)
		mapa[{j.first.second,j.first.first}]=j.second;

	for(auto j=mapa.begin();j!=mapa.end();j++){
		if((*j).first.first==0)continue;
		auto next = j;
		next++;
		if(next==mapa.end())break;
		if((*next).first.first==(*j).first.first){
			int a =(*j).first.second, b = (*next).first.second;
			auto &pom = poziomy[(*j).first.first];
			if(upper_bound(pom.begin(), pom.end(), make_pair(a,1000000000))==upper_bound(pom.begin(), pom.end(), make_pair(b,1000000000))){
				graf[(*next).second].push_back({(*j).second, x[(*next).first.second]-x[(*j).first.second]});
				graf[(*j).second].push_back({(*next).second, x[(*next).first.second]-x[(*j).first.second]});
			}
		}
	}
	priority_queue<pair<long long, int>>kolejka;
	dist[0] = 1;
	kolejka.push({-1,0});
	while(kolejka.size()){
		auto a = kolejka.top();
		kolejka.pop();
		if(odw[a.second])continue;
		odw[a.second]=1;
		for(auto j: graf[a.second]){
			if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){
				dist[j.first]=dist[a.second]+j.second;
				kolejka.push({-dist[j.first], j.first});
			}
		}
	}
	return dist[1]-1;
}

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