제출 #163334

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163334		alishahali1382	Pinball (JOI14_pinball)	C++14	100 / 100	302 ms	30764 KiB

pinball

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 300010, LOG=20;

struct Segment{
	ll seg[MAXN<<2];
	Segment(){
		memset(seg, 63, sizeof(seg));
	}
	void Set(int id, int tl, int tr, int pos, ll val){
		if (pos<tl || tr<=pos) return ;
		if (tr-tl==1){
			seg[id]=val;
			return ;
		}
		int mid=(tl+tr)>>1;
		Set(id<<1, tl, mid, pos, val);
		Set(id<<1 | 1, mid, tr, pos, val);
		seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
	}
	ll Get(int id, int tl, int tr, int l, int r){
		if (r<=tl || tr<=l) return seg[0];
		if (l<=tl && tr<=r) return seg[id];
		int mid=(tl+tr)>>1;
		return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
	}
} Dp1, Dp2;

ll n, m, k, u, v, x, y, t, a, b, ans=INF;
int A[MAXN], B[MAXN], C[MAXN], D[MAXN];
ll dp1[MAXN], dp2[MAXN];
vector<int> comp;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>m>>n;
	for (int i=1; i<=m; i++){
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		comp.pb(A[i]);
		comp.pb(B[i]);
		comp.pb(C[i]);
	}
	comp.pb(1);
	comp.pb(n);
	//comp.pb(n+1);
	sort(all(comp));
	comp.resize(unique(all(comp))-comp.begin());
	n=comp.size();
	//debugv(comp)
	for (int i=1; i<=m; i++){
		A[i]=lower_bound(all(comp), A[i])-comp.begin();
		B[i]=lower_bound(all(comp), B[i])-comp.begin();
		C[i]=lower_bound(all(comp), C[i])-comp.begin();
		//cerr<<A[i]<<" "<<C[i]<<' '<<B[i]<<' '<<"  "<<D[i]<<endl;
	}
	
	memset(dp1, 63, sizeof(dp1));
	memset(dp2, 63, sizeof(dp2));
	dp1[0]=0;
	dp2[n-1]=0;
	Dp1.Set(1, 0, n, 0, 0);
	Dp2.Set(1, 0, n, n-1, 0);
	
	for (int i=1; i<=m; i++){
		ll x=Dp1.Get(1, 0, n, A[i], B[i]+1);
		ll y=Dp2.Get(1, 0, n, A[i], B[i]+1);
		ans=min(ans, x+y+D[i]);
		
		if (x+D[i]<dp1[C[i]]){
			//cerr<<"update dp1 : "<<i<<"  "<<C[i]<<' '<<x+D[i]<<endl<<endl;
			dp1[C[i]]=x+D[i];
			Dp1.Set(1, 0, n, C[i], dp1[C[i]]);
		}
		if (y+D[i]<dp2[C[i]]){
			/*
			debug(y)
			cerr<<"update dp2 : "<<i<<"  "<<C[i]<<' '<<y+D[i]<<endl<<endl;
			*/
			dp2[C[i]]=y+D[i];
			Dp2.Set(1, 0, n, C[i], dp2[C[i]]);
		}
	}
	
	if (ans>=INF) ans=-1;
	cout<<ans<<'\n';
	
	return 0;
}

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