Submission #377455

#	Time	Username	Problem	Language	Result	Execution time	Memory
377455		reymontada61	Pinball (JOI14_pinball)	C++14	100 / 100	894 ms	259436 KiB

pinball

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

int n, m;
const int MXN = 100005;
int l[MXN], r[MXN], to[MXN], c[MXN];

int lec[MXN], ric[MXN];

int MXE = LLONG_MAX / 10;

int ans = MXE;
bool can;

struct LzSegmentTree {
	
	int seg[70*MXN];
	int le[70*MXN];
	int ri[70*MXN]; 
	
	int n, nx;
	
	LzSegmentTree(int N) {
		seg[0] = seg[1] = MXE;
		le[0] = le[1] = 0;
		ri[0] = ri[1] = 0;
		nx = 1;
	}
	
	int get() {
		nx++;
		seg[nx] = MXE;
		le[nx] = 0;
		ri[nx] = 0;
		return nx;
	}
	
	void update(int ind, int l, int r, int pos, int by) {
		if (l == r) {
			seg[ind] = min(seg[ind], by);
			return;
		}
		int m = (l + r) / 2;
		if (pos <= m) {
			if (le[ind] == 0) le[ind] = get();
			update(le[ind], l, m, pos, by);
		}
		else {
			if (ri[ind] == 0) ri[ind] = get();
			update(ri[ind], m+1, r, pos, by);
		}
		seg[ind] = min(seg[le[ind]], seg[ri[ind]]);
	}
	
	int query(int ind, int l, int r, int ql, int qr) {
		if (ql <= l && r <= qr) {
			return seg[ind];
		}
		if (ql > r || qr < l) return MXE;
		if (le[ind] == 0) le[ind] = get();
		if (ri[ind] == 0) ri[ind] = get();
		int m = (l + r) / 2;
		return min(query(le[ind], l, m, ql, qr), query(ri[ind], m+1, r, ql, qr));
	}
	
};

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	cin >> m >> n;
	for (int i=1; i<=m; i++) {
		cin >> l[i] >> r[i] >> to[i] >> c[i];
	}
	
	LzSegmentTree onL(n), onR(n);
	
	for (int i=1; i<=m; i++) {
		if (l[i] == 1) {
			lec[i] = c[i];
		}
		else {
			lec[i] = min(MXE, c[i] + onL.query(1, 1, n, l[i], r[i]));
		}
		
		if (r[i] == n) {
			ric[i] = c[i];
		}
		else {
			ric[i] = min(MXE, c[i] + onR.query(1, 1, n, l[i], r[i]));
		}
		
		onL.update(1, 1, n, to[i], lec[i]);
		onR.update(1, 1, n, to[i], ric[i]);
		
		if (lec[i] >= MXE || ric[i] >= MXE) continue;
		
		can = true;
		ans = min(ans, lec[i] + ric[i] - c[i]);
			
	}
	
	if (can) cout << ans << endl;
	else cout << -1 << endl;
	
}

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