Submission #1216894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216894		loiiii12358	Sky Walking (IOI19_walk)	C++20	15 / 100	220 ms	28436 KiB

walk

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

struct segment{
	int umi,dmi;
	segment(){
		umi=dmi=1e18;
	}
	segment(int a,int b){
		umi=a;
		dmi=b;
	}
};

segment merge(segment a,segment b){
	return segment(min(a.umi,b.umi),min(a.dmi,b.dmi));
}

int N;
vector<segment> seg;

void update(int id,int l,int r,int x,int a,int b){
	if(l==r){
		seg[id]=segment(a,b);
		return;
	}
	int m=(l+r)/2;
	if(x<=m){
		update(id*2,l,m,x,a,b);
	}else{
		update(id*2+1,m+1,r,x,a,b);
	}
	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<int,int> tran;
vector<int> to,tmp;
vector<vector<int>> add,del;

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) {
	int n=x.size(),m=l.size();
	add.resize(n);del.resize(n);
	for(int i=0;i<m;i++){
		tran[y[i]]=0;
	}
	tran[0]=0;
	for(auto i=tran.begin();i!=tran.end();i++){
		to.push_back(i->first);
		i->second=cnt++;
	}
	seg.resize(4*cnt);
	for(int i=0;i<m;i++){
		add[l[i]].push_back(tran[y[i]]);
		del[r[i]].push_back(tran[y[i]]);
	}
	del[0].push_back(0);
	update(1,0,cnt-1,0,0,0);
	for(int i=0;i<n-1;i++){
		tmp.clear();
		int b=(--tran.upper_bound(h[i]))->second;
		for(int j=0;j<add[i].size();j++){
			if(add[i][j]>b){
				tmp.push_back(1e18);
				continue;
			}
			segment hi=query(1,0,cnt-1,add[i][j],b);
			segment lo=query(1,0,cnt-1,0,add[i][j]);
			int self=min(hi.umi-to[add[i][j]],lo.dmi+to[add[i][j]]);
			tmp.push_back(self);
		}
		for(int j=0;j<del[i].size();j++){
			update(1,0,cnt-1,del[i][j],1e18,1e18);
		}
		for(int j=0;j<add[i].size();j++){
			if(tmp[j]>1e16){
				continue;
			}
			update(1,0,cnt-1,add[i][j],tmp[j]+to[add[i][j]],tmp[j]-to[add[i][j]]);
		}
	}
	segment ans=query(1,0,cnt-1,0,cnt-1);
	if(ans.umi>1e16){
		return -1;
	}
	return x[n-1]-x[0]+ans.umi;
}

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