Submission #1039011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039011		amirhoseinfar1385	Sky Walking (IOI19_walk)	C++17	0 / 100	1489 ms	742944 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,kaf=1e9+5,inf=1e18+5;
long long n,allx[maxn],q,allh[maxn];
vector<long long>addq[maxn],delq[maxn];

struct qu{
	long long l,r,res,y;
}allq[maxn];

struct segment{
	struct node{
		long long mina,cl,cr;
		set<pair<long long,long long>>st;
		node(){
			mina=inf;
			cl=cr=-1;
			st.insert(make_pair(inf,-1));
		}
	}fakenode;
	vector<node>seg;
	segment(){
		seg.resize(2);
	}
	long long getl(long long i){
		if(seg[i].cl==-1){
			seg.push_back(fakenode);
			seg[i].cl=(long long)seg.size()-1;
		}
		return seg[i].cl;
	}
	long long getr(long long i){
		if(seg[i].cr==-1){
			seg.push_back(fakenode);
			seg[i].cr=(long long)seg.size()-1;
		}
		return seg[i].cr;
	}
	void upd(long long i,long long l,long long r,long long tl,long long tr,pair<long long,long long> w){
		//cout<<"upd: "<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<i<<endl;
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].st.insert(w);
			seg[i].mina=(*seg[i].st.begin()).first;
			return ;
		}
		long long m=(l+r)>>1;
		upd(getl(i),l,m,tl,tr,w);
		upd(getr(i),m+1,r,tl,tr,w);
		seg[i].mina=min(seg[getl(i)].mina,seg[getr(i)].mina);
	}
	void erase(long long i,long long l,long long r,long long tl,long long tr,pair<long long,long long> w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			seg[i].st.insert(w);
			seg[i].mina=(*seg[i].st.begin()).first;
			return ;
		}
		long long m=(l+r)>>1;
		erase(getl(i),l,m,tl,tr,w);
		erase(getr(i),m+1,r,tl,tr,w);
		seg[i].mina=min(seg[getl(i)].mina,seg[getr(i)].mina);
	}
	long long pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr||i==-1){
			return inf;
		}
		if(l>=tl&&r<=tr){
			return seg[i].mina;
		}
		long long m=(l+r)>>1;
		return min(pors(seg[i].cl,l,m,tl,tr),pors(seg[i].cr,m+1,r,tl,tr));
	}
}segmanf,segmos;


long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y,int s, int g) {
	n=x.size();
	q=(long long)l.size();
	for(long long i=0;i<n;i++){
		allx[i]=x[i];
		allh[i]=h[i];
	}
	if(s!=0||g!=n-1){
		exit(23);
		return 0;
	}
	for(long long i=0;i<q;i++){
		allq[i].l=l[i];
		allq[i].r=r[i];
		allq[i].y=y[i];
		addq[l[i]].push_back(i);
		delq[r[i]].push_back(i);
	}
	long long mainres=inf;
	int cnt=0;
	for(long long i=0;i<n;i++){
		if(i==n-1){
			mainres=segmos.pors(1,0,kaf-1,0,kaf-1)+allx[i];
		}
		for(auto x:addq[i]){
			if(i==0){
				allq[x].res=allq[x].y;
			}else{
				allq[x].res=min(segmanf.pors(1,0,kaf-1,0,allq[x].y)+allq[x].y,segmos.pors(1,0,kaf-1,allq[x].y,allh[i])-allq[x].y)+allx[i];
			}
			//cout<<allq[x].l<<" "<<allq[x].r<<" "<<allq[x].y<<" "<<allq[x].res<<endl;
			segmos.upd(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[i]+allq[x].y,x));
			segmanf.upd(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[i]-allq[x].y,x));
			cnt++;
		}
		for(auto x:delq[i]){
			segmos.erase(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[allq[x].l]+allq[x].y,x));
			segmanf.erase(1,0,kaf-1,allq[x].y,allq[x].y,make_pair(allq[x].res-allx[allq[x].l]-allq[x].y,x));
			cnt--;
		}
		if(i!=n-1&&cnt==0){
			return -1;
		}
	}
	if(mainres>=inf){
		mainres=-1;
	}
	return mainres;
}

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