oj.uz

Submission #377455

# Submission time Handle Problem Language Result Execution time Memory
377455 2021-03-14T08:37:37 Z reymontada61 Pinball (JOI14_pinball) C++14
100 / 100
 894 ms 259436 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 / 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1388 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1388 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 2 ms 1004 KB Output is correct
17 Correct 7 ms 2156 KB Output is correct
18 Correct 3 ms 492 KB Output is correct
19 Correct 6 ms 4076 KB Output is correct
20 Correct 4 ms 1644 KB Output is correct
21 Correct 2 ms 1388 KB Output is correct
22 Correct 7 ms 3948 KB Output is correct
23 Correct 6 ms 4460 KB Output is correct
24 Correct 8 ms 4460 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 2 ms 1260 KB Output is correct
13 Correct 2 ms 1260 KB Output is correct
14 Correct 2 ms 1388 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 2 ms 1004 KB Output is correct
17 Correct 7 ms 2156 KB Output is correct
18 Correct 3 ms 492 KB Output is correct
19 Correct 6 ms 4076 KB Output is correct
20 Correct 4 ms 1644 KB Output is correct
21 Correct 2 ms 1388 KB Output is correct
22 Correct 7 ms 3948 KB Output is correct
23 Correct 6 ms 4460 KB Output is correct
24 Correct 8 ms 4460 KB Output is correct
25 Correct 35 ms 7532 KB Output is correct
26 Correct 199 ms 37484 KB Output is correct
27 Correct 522 ms 67776 KB Output is correct
28 Correct 317 ms 6252 KB Output is correct
29 Correct 404 ms 78316 KB Output is correct
30 Correct 636 ms 19260 KB Output is correct
31 Correct 878 ms 142828 KB Output is correct
32 Correct 832 ms 100460 KB Output is correct
33 Correct 70 ms 31340 KB Output is correct
34 Correct 406 ms 126060 KB Output is correct
35 Correct 459 ms 253228 KB Output is correct
36 Correct 894 ms 259436 KB Output is correct
37 Correct 713 ms 257628 KB Output is correct
38 Correct 647 ms 257004 KB Output is correct