oj.uz

답안 #1039013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039013 2024-07-30T10:48:17 Z amirhoseinfar1385 Sky Walking (IOI19_walk) C++17
0 / 100
 1394 ms 741232 KB 
#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;
	if(n==1){
		return 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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 6492 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 4956 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 15528 KB Output is correct
2 Correct 1394 ms 736664 KB Output is correct
3 Correct 1285 ms 733476 KB Output is correct
4 Correct 1251 ms 736652 KB Output is correct
5 Correct 1275 ms 734912 KB Output is correct
6 Correct 1299 ms 741232 KB Output is correct
7 Correct 577 ms 381964 KB Output is correct
8 Incorrect 995 ms 741104 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 15528 KB Output is correct
2 Correct 1394 ms 736664 KB Output is correct
3 Correct 1285 ms 733476 KB Output is correct
4 Correct 1251 ms 736652 KB Output is correct
5 Correct 1275 ms 734912 KB Output is correct
6 Correct 1299 ms 741232 KB Output is correct
7 Correct 577 ms 381964 KB Output is correct
8 Incorrect 995 ms 741104 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 6492 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -