제출 #1271613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271613		coderpemula	Pinball (JOI14_pinball)	C++20	100 / 100	159 ms	12228 KiB

pinball

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second

using namespace std;
int tree1[400001],tree3[400001],lft[100001],rgt[100001];
void upd1(int node, int st, int en, int point){
	if(st > point or en < point) return;
	if(st == en) tree1[node] = lft[st];
	else{
		int mid = (st+en)/2;
		upd1(node*2,st,mid,point);
		upd1(node*2+1,mid+1,en,point);
		tree1[node] = min(tree1[node*2],tree1[node*2+1]);
	}
}
void upd3(int node, int st, int en, int point){
	if(st > point or en < point) return;
	if(st == en) tree3[node] = rgt[st];
	else{
		int mid = (st+en)/2;
		upd3(node*2,st,mid,point);
		upd3(node*2+1,mid+1,en,point);
		tree3[node] = min(tree3[node*2],tree3[node*2+1]);
	}
}
int query1(int node, int st, int en, int L, int R){
	if(st > R or en < L) return 1e18;
	if(st >= L and en <= R) return tree1[node];
	int mid = (st+en)/2;
	int q1 = query1(node*2,st,mid,L,R);
	int q3 = query1(node*2+1,mid+1,en,L,R);
	return min(q1,q3);
}
int query3(int node, int st, int en, int L, int R){
	if(st > R or en < L) return 1e18;
	if(st >= L and en <= R) return tree3[node];
	int mid = (st+en)/2;
	int q1 = query3(node*2,st,mid,L,R);
	int q3 = query3(node*2+1,mid+1,en,L,R);
	return min(q1,q3);
}
signed main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int m,n,i,j;
	cin>>m>>n;
	int anu[m+1],bnu[m+1],cnu[m+1],dnu[m+1],ans=1e18,ind;
	vector<int>v;
	for(i=1;i<=m;i++){
		cin>>anu[i]>>bnu[i]>>cnu[i]>>dnu[i];
		v.pb(cnu[i]);
	}
	for(i=1;i<=4*m;i++) tree1[i] = tree3[i] = 1e18;
	for(i=1;i<=m;i++) lft[i] = rgt[i] = 1e18;
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	// 2 segtree
	// 1 -> minimum buat sampe L
	// 2 -> minimum buat sampe R
	int p = v.size();
	for(i=1;i<=m;i++){
		if(anu[i] == 1 and bnu[i] == n) ans = min(ans,dnu[i]);
		int idx = lower_bound(v.begin(),v.end(),cnu[i])-v.begin()+1;
		if(anu[i] == 1){
			// update index c[i]
			lft[idx] = min(lft[idx],dnu[i]);
			upd1(1,1,p,idx);
			// cari rgt
			// >= anu[i]
			ind = lower_bound(v.begin(),v.end(),anu[i])-v.begin()+1;
			// <= bnu[i]
			int kanan = upper_bound(v.begin(),v.end(),bnu[i])-v.begin();
			int tambah = query3(1,1,p,ind,kanan);
			rgt[idx] = min(rgt[idx],dnu[i]+tambah);
			upd3(1,1,p,idx);
			ans = min(ans,tambah+dnu[i]);
		}
		if(bnu[i] == n){
			int idx = lower_bound(v.begin(),v.end(),cnu[i])-v.begin()+1;
			rgt[idx] = min(rgt[idx],dnu[i]);
			//cout<<rgt[idx]<<" ";
			upd3(1,1,p,idx);
			//cout<<query3(1,1,p,idx,idx)<<endl;
			idx = lower_bound(v.begin(),v.end(),anu[i])-v.begin()+1;
			int kanan = upper_bound(v.begin(),v.end(),bnu[i])-v.begin();
			int tambah = query1(1,1,p,idx,kanan);
			lft[idx] = min(lft[idx],dnu[i]+tambah);
			ans = min(ans,tambah+dnu[i]);
		}
		ind = lower_bound(v.begin(),v.end(),anu[i])-v.begin()+1;
		int kanan = upper_bound(v.begin(),v.end(),bnu[i])-v.begin();
		int kiri = query1(1,1,p,ind,kanan), kan = query3(1,1,p,ind,kanan);
		rgt[idx] = min(rgt[idx],kan+dnu[i]);
		upd3(1,1,p,idx);
		lft[idx] = min(lft[idx],kiri+dnu[i]);
		upd1(1,1,p,idx);
		//cout<<i<<" "<<kiri<<" "<<kan<<endl;
		ans = min(ans,kiri+kan+dnu[i]);
	}
	if(ans == 1e18) ans = -1;
	cout<<ans;
	
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49