oj.uz

답안 #377431

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377431 2021-03-14T08:08:37 Z reymontada61 Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 492 KB 
#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 / 2;

int ans = MXE;
bool can;


struct LzSegmentTree {
	
	vector<int> seg;
	vector<int> le;
	vector<int> ri; 
	
	int n, nx;
	
	LzSegmentTree(int N) {
		seg = {MXE, MXE};
		le = {0, 0};
		ri = {0, 0};
		nx = 1;
	}
	
	int get() {
		nx++;
		seg.push_back(MXE);
		le.push_back(0);
		ri.push_back(0);
		return nx;
	}
	
	void update(int ind, int l, int r, int pos, int by) {
		// point set
		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) {
		// range min
		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() {

	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
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -