Submission #1216836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216836		loiiii12358	Sky Walking (IOI19_walk)	C++20	10 / 100	19 ms	3720 KiB

walk

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

struct segment{
	int pos,ma;
	segment(){
		pos=ma=0;
	}
	segment(int a,int b){
		pos=a;
		ma=b;
	}
};

segment merge(segment a,segment b){
	segment ans;
	if(a.ma>b.ma){
		ans=a;
	}else{
		ans=b;
	}
	return ans;
}

int N;
vector<int> H,X;
vector<segment> seg;

void build(int id,int l,int r){
	if(l==r){
		seg[id]=segment(l,H[l]);
		return;
	}
	int m=(l+r)/2;
	build(id*2,l,m);
	build(id*2+1,m+1,r);
	seg[id]=merge(seg[id*2],seg[id*2+1]);
}

segment query(int id,int l,int r,int L,int R){
	if(l>R||r<L){
		return segment();
	}else if(l>=L&&r<=R){
		return seg[id];
	}
	int m=(l+r)/2;
	return merge(query(id*2,l,m,L,R),query(id*2+1,m+1,r,L,R));
}

int cnt;
map<pair<int,int>,int> tran;
vector<set<int>> nodes;
vector<vector<pair<int,int>>> edges;
priority_queue<pair<int,int>> pq;
vector<int> dist;

void add(int l,int r,int y){
	if(l+1>r-1){
		if(!tran.count({X[l],y})){
			tran[{X[l],y}]=cnt++;
			nodes[l].insert(y);
		}
		if(!tran.count({X[r],y})){
			tran[{X[r],y}]=cnt++;
			nodes[r].insert(y);
		}
		edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]});
		edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]});
		return;
	}
	segment tmp=query(1,0,N-1,l+1,r-1);
	if(tmp.ma>=y){
		add(l,tmp.pos,y);
		add(tmp.pos,r,y);
	}else{
		if(!tran.count({X[l],y})){
			tran[{X[l],y}]=cnt++;
			nodes[l].insert(y);
		}
		if(!tran.count({X[r],y})){
			tran[{X[r],y}]=cnt++;
			nodes[r].insert(y);
		}
		edges[tran[{X[r],y}]].push_back({tran[{X[l],y}],X[r]-X[l]});
		edges[tran[{X[l],y}]].push_back({tran[{X[r],y}],X[r]-X[l]});
	}
}

long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t s, int32_t g) {
	N=x.size();
	int m=l.size();
	H.resize(N);seg.resize(4*N);X.resize(N);edges.resize(N*m);nodes.resize(N);
	for(int i=0;i<N;i++){
		H[i]=h[i];
		X[i]=x[i];
	}
	build(1,0,N-1);
	for(int i=0;i<m;i++){
		add(l[i],r[i],y[i]);
	}
	tran[{x[s],0}]=cnt++;tran[{x[g],0}]=cnt++;
	nodes[s].insert(0);nodes[g].insert(0);
	for(int i=0;i<N;i++){
		int last=-1;
		for(auto j:nodes[i]){
			if(last!=-1){
				edges[tran[{x[i],last}]].push_back({tran[{x[i],j}],j-last});
				edges[tran[{x[i],j}]].push_back({tran[{x[i],last}],j-last});
			}
			last=j;
		}
	}
	dist.resize(cnt,1e18);
	pq.push({0,tran[{x[s],0}]});
	dist[tran[{x[s],0}]]=0;
	while(!pq.empty()){
		int u=pq.top().second,t=-pq.top().first;
		pq.pop();
		if(dist[u]!=t){
			continue;
		}
		for(int i=0;i<edges[u].size();i++){
			int v=edges[u][i].first;
			if(dist[v]>t+edges[u][i].second){
				dist[v]=t+edges[u][i].second;
				pq.push({-dist[v],v});
			}
		}
	}
	if(dist[tran[{x[g],0}]]==1e18){
		return -1;
	}
	return dist[tran[{x[g],0}]];
}

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