제출 #117362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
117362		Adhyyan1252	Pinball (JOI14_pinball)	C++11	100 / 100	385 ms	16136 KiB

pinball

#include<bits/stdc++.h>

using namespace std;

#define int long long
#define INF 1e16
//825 

struct segtree{
	vector<int> t;
	int sz;
	
	segtree(int size){
		sz = size;
		t = vector<int>(4*size, INF);
	}
	
	void upd(int i, int s, int e, int indx, int val){
		if(s == e){
			t[i] = min(val, t[i]);
			return;
		}
		int m = (s + e)/2;
		if(indx <= m){
			upd(i*2, s, m, indx, val);
		}else{
			upd(i*2+1, m+1, e, indx, val);
		}
		t[i] = min(t[i*2], t[i*2+1]);
	}
	
	int query(int i, int s, int e, int l, int r){
		if(l > r) return INF;
		if(l <= s && e <= r) return t[i	];
		if(s > r || e < l) return INF;
		int m = (s + e)/2;
		return min(query(i*2, s, m, l, r), query(i*2+1, m+1, e, l, r));
	}
};

signed main(){
	int n, m; cin>>m>>n;
	vector<int> a, b, c, d;
	a.resize(m);
	b.resize(m);
	c.resize(m);
	d.resize(m);
	
	for(int i = 0; i < m; i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}

	
	vector<pair<int, int> > lc, rc;
	for(int i = 0; i < m; i++){
		lc.push_back({c[i], i});
	}
	sort(lc.begin(), lc.end());
	
	vector<int> lindx(m);
	for(int i = 0; i < m; i++){
		lindx[lc[i].second] = i;
	}

	
	segtree left(m), right(m);
	
	int ans = INF;
	for(int i = 0; i < m; i++){
	
		//upd this device now
		//the index is lindx[i]
		//find the range of vertices for query
		//do binary search on lc array with a, b
		
		
		pair<int, int> ls = {a[i], -1};
		pair<int, int> rs = {b[i], INF};
		int l = lower_bound(lc.begin(), lc.end(),ls)-lc.begin();
		int r = upper_bound(lc.begin(), lc.end(),rs)-lc.begin()-1;
		//cout<<"RANGE: "<<i<<" : "<<lindx[i]<<" "<<l<<" "<<r<<endl;
		int Lnval = left.query(1, 0, left.sz-1, l, r) + d[i];
		
		if(a[i] == 1) Lnval = d[i];
		
		left.upd(1, 0, left.sz-1, lindx[i], Lnval);
		
		int Rnval = right.query(1, 0, right.sz-1, l, r) + d[i];
		if(b[i] == n) Rnval = d[i];
		right.upd(1, 0, right.sz-1, lindx[i], Rnval);
		
		ans = min(ans, Lnval + Rnval - d[i]);
		
		//cout<<i<<": "<<Lnval<<" "<<Rnval<<endl;
	}
	
	if(ans >= INF) cout<<-1<<endl;
	else cout<<ans<<endl;
}

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