제출 #235320

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235320		Blagojce	Pinball (JOI14_pinball)	C++11	0 / 100	42 ms	78584 KiB

pinball

#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e17;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 5e6 + 5;

ll seg1[mxn];
ll seg2[mxn];
void update(int k, int l, int r, int pos, ll val){
	
	if(r < pos || pos < l) return;
	if(l == r){
		seg1[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	update(k * 2, l, mid, pos, val);
	update(k * 2 + 1, mid + 1, r, pos, val);
	seg1[k] = min(seg1[k * 2], seg1[k * 2 + 1]);


}
ll query(int k, int l, int r, int x, int y){
	if(r < x || y < l) return inf;
	if(x <= l && r <= y){
		return seg1[k];
	}
	int mid = (l + r) / 2;
	return min(query(k * 2, l, mid, x, y), query(k * 2 + 1, mid + 1, r, x, y));
}

void update2(int k, int l, int r, int pos, ll val){
	if(r < pos || pos < l) return;
	if(l == r){
		seg2[k] = val;
		return;
	}
	int mid = (l + r) / 2;
	update2(k * 2, l, mid, pos, val);
	update2(k * 2 + 1, mid + 1, r, pos, val);
	seg2[k] = min(seg2[k * 2], seg2[k * 2 + 1]);
}
ll query2(int k, int l, int r, int x, int y){
	if(r < x || y < l) return inf;
	if(x <= l && r <= y){
		return seg2[k];
	}
	int mid = (l + r) /2 ;
	return min(query2(k * 2, l, mid, x, y), query2(k * 2 + 1, mid + 1, r, x, y));
}

int maxbound = 1e5;

void solve(){

	fr(i,0 , mxn){
		seg1[i] = seg2[i] = inf;
	}

	int M, N;
	cin >> M >> N;
	int a[M], b[M], c[M], d[M];
	vector<pair<int, pii> > v;
	
	fr(i, 0, M){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		v.pb({a[i], {-1, i}});
		v.pb({b[i], {1, i}});
		v.pb({c[i], {0, i}});
			
	}
	sort(all(v));
	int val = 0;
	if(v[0].st != 1 || v.back().st != N){
		cout << -1<<endl;
		return;
	}
	
	if(v[0].nd.st == -1) a[v[0].nd.nd] = val;
	
	else if(v[0].nd.st == 1) b[v[0].nd.nd] = val;
	else c[v[0].nd.nd] = val;
	
	
	fr(i, 1, (int)(v.size())){
		if(v[i].st != v[i - 1].st) val ++;
		if(v[i].nd.st == -1) a[v[i].nd.nd] = val;
		else if(v[i].nd.st == 1) b[v[i].nd.nd] = val;
		else c[v[i].nd.nd] = val;
	}
	
	maxbound = val;
	
	
	

	
	
	ll ans = inf;
	fr(i, 0, M){
		int l = a[i], r = b[i], mid = c[i];
		ll costleft = d[i];

		if(l != 0){
			costleft = min(inf, query(1, 0, maxbound, l, r) + d[i]);
		}
		update(1, 0, maxbound, mid, costleft);
		
		
		ll costright = d[i];	
		if(r != maxbound){
			costright = min(inf, query2(1, 0, maxbound, l, r) + d[i]);
		}
		
		update2(1, 0, maxbound, mid, costright);
		
		ans = min(ans, costleft + costright - d[i]);
	}
	
	if(ans == inf) cout << -1 << endl;
	else cout << ans << endl;

}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	solve();
}

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