Submission #108876

#	Time	Username	Problem	Language	Result	Execution time	Memory
108876		Diuven	Pinball (JOI14_pinball)	C++14	100 / 100	335 ms	10456 KiB

pinball

#include <bits/stdc++.h>
using namespace std;

typedef long long lint;
typedef pair<int, int> pii;

const int INF = 2e9;
const int MOD = 1e9+7;
const int MAX = 1e5+10;
const lint LNF = 2e18;

inline lint _min(lint a, lint b){ return a<b ? a : b; }

/*
cost(i): 각 장치 i에 대해서, 이 장치가 마지막일 최소 비용.
L[x], R[x]를 관리한다.
L[x]: 1에서 x로 갈 최소 비용
R[x]: n에서 x로 갈 최소 비용
cost(i) = min_{A[i]<=k<=B[i]}(L[k]) + min_{A[i]<=k<=B[i]}(R[k]) + D[i]
만약 A[i]<=k<=B[i]에 대해서, L[k]<LNF이면 L[C[i]] = min(L[k]) + D[i]
*/

class Coord_t{
	vector<int> P;
  public:
	void add(int p){
		P.push_back(p);
	}
	int compress(){
		sort(P.begin(), P.end());
		int res = unique(P.begin(), P.end()) - P.begin();
		P.resize(res);
		return res;
	}
	int get_lo(int p){
		// 이하인 최대
		return upper_bound(P.begin(), P.end(), p) - P.begin() - 1 + 1;
	}
	int get_hi(int p){
		// 이상인 최소
		return lower_bound(P.begin(), P.end(), p) - P.begin() + 1;
	}
	int get(int p){
		if(!binary_search(P.begin(), P.end(), p)){ cerr<<"SHIT\n"; exit(42); }
		return get_lo(p);
	}
} Coord;

class Seg_t{
	int n;
	lint T[1<<18];
	void add(int v, int s, int e, int p, lint val){
		if(s==e){ T[v] = _min(T[v], val); return; }
		int mid = (s+e)/2;
		if(p<=mid) add(v*2,s,mid,p,val);
		else add(v*2+1,mid+1,e,p,val);
		T[v] = _min(T[v*2], T[v*2+1]);
	}
	lint mn(int v, int s, int e, int l, int r){
		if(e<l || r<s) return LNF;
		if(l<=s && e<=r) return T[v];
		return _min(mn(v*2,s,(s+e)/2,l,r), mn(v*2+1,(s+e)/2+1,e,l,r));
	}
  public:
	void init(int sz){
		n = sz;
		for(int i=0; i<(1<<18); i++) T[i] = LNF;
	}
	void add(int p, lint val){
		p = Coord.get(p);
		if(p<1 || n<p){ cerr<<"SHIIT\n"; exit(42); }
		add(1,1,n,p,val);
	}
	lint mn(int l, int r){
		l = Coord.get_hi(l), r = Coord.get_lo(r);
		if(l>n || r<1) return LNF;
		return mn(1,1,n,l,r);
	}
} LSeg, RSeg;

int main(){
	ios::sync_with_stdio(0); cin.tie(0);

	static int A[MAX], B[MAX], C[MAX], D[MAX];

	int n, m; cin>>m>>n;
	for(int i=1; i<=m; i++){
		cin>>A[i]>>B[i]>>C[i]>>D[i];
		Coord.add(C[i]);
	}

	Coord.add(1); Coord.add(n);

	int sz = Coord.compress();
	LSeg.init(sz); RSeg.init(sz);

	LSeg.add(1, 0); RSeg.add(n, 0);

	lint ans = LNF;

	for(int i=1; i<=m; i++){
		
		// for(int i=1; i<=sz; i++){
		// 	int x = Coord.P[i-1];
		// 	cout<<LSeg.mn(x,x)<<' '<<RSeg.mn(x,x)<<'\n';
		// }
		// cout<<'\n';

		lint lft = LSeg.mn(A[i], B[i]);
		lint rig = RSeg.mn(A[i], B[i]);
		ans = min(ans, lft+rig+D[i]);
		if(lft<LNF) LSeg.add(C[i], lft+D[i]);
		if(rig<LNF) RSeg.add(C[i], rig+D[i]);
	}

	if(ans>=LNF) ans = -1;

	cout<<ans<<'\n';

	return 0;
}

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