oj.uz

Submission #36074

# Submission time Handle Problem Language Result Execution time Memory
36074 2017-12-05T06:00:03 Z minkank Pinball (JOI14_pinball) C++14
100 / 100
 326 ms 28744 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;

struct Device {
	int l, r, mid, cost;
};

struct SegmentTree {
	#define mid ((l + r) >> 1)
	long long it[N * 4];
	void init() { for(int i = 0; i < N * 4; ++i) it[i] = 1e18; }
	void update(int node, int l, int r, int p, long long val) {
		if(l > p || r < p) return;
		if(l == r) { it[node] = min(it[node], val); return; }
		update(node << 1, l, mid, p, val); update(node << 1 | 1, mid + 1, r, p, val);
		it[node] = min(it[node << 1], it[node << 1 | 1]);
	}
	long long get(int node, int l, int r, int p, int q) {
		if(l > q || r < p) return 1e18;
		if(p <= l && r <= q) return it[node];
		return min(get(node << 1, l, mid, p, q), get(node << 1 | 1, mid +  1, r, p, q));
	}
	#undef mid
};

int n, m, Start, End;
Device d[N];
vector<int> Value;
SegmentTree Left, Right;
long long ans = 1e18;

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	if(n == 1) return cout << 0, 0;
	for(int i = 1; i <= n; ++i) {
		int l, r, mid, cost;
		cin >> l >> r >> mid >> cost;
		d[i] = {l, r, mid, cost};
		Value.push_back(l);
		Value.push_back(r);
		Value.push_back(mid);
	}
	Value.push_back(1); Value.push_back(m);
	sort(Value.begin(), Value.end());
	Value.resize(distance(Value.begin(), unique(Value.begin(), Value.end())));
	for(int i = 1; i <= n; ++i) {
		d[i].l = lower_bound(Value.begin(), Value.end(), d[i].l) - Value.begin();
		d[i].r = lower_bound(Value.begin(), Value.end(), d[i].r) - Value.begin();
		d[i].mid = lower_bound(Value.begin(), Value.end(), d[i].mid) - Value.begin();
	}
	Left.init(); Right.init();
	Left.update(1, 0, Value.size() - 1, 0, 0);
	Right.update(1, 0, Value.size() - 1, Value.size() - 1, 0);
	for(int i = 1; i <= n; ++i) {
		long long valL = Left.get(1, 0, Value.size() - 1, d[i].l, d[i].r),
				  valR = Right.get(1, 0, Value.size() - 1, d[i].l, d[i].r);
		ans = min(ans, valL + valR + d[i].cost);
		Left.update(1, 0, Value.size() - 1, d[i].mid, valL + d[i].cost);
		Right.update(1, 0, Value.size() - 1, d[i].mid, valR + d[i].cost);
	}
	if(ans == 1e18) cout << -1;
	else cout << ans;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 25632 KB Output is correct
2 Correct 0 ms 25632 KB Output is correct
3 Correct 6 ms 25632 KB Output is correct
4 Correct 0 ms 25632 KB Output is correct
5 Correct 0 ms 25632 KB Output is correct
6 Correct 0 ms 25632 KB Output is correct

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25792 KB Output is correct
2 Correct 66 ms 26440 KB Output is correct
3 Correct 209 ms 27208 KB Output is correct
4 Correct 193 ms 28744 KB Output is correct
5 Correct 146 ms 27208 KB Output is correct
6 Correct 226 ms 28744 KB Output is correct
7 Correct 296 ms 28744 KB Output is correct
8 Correct 283 ms 28744 KB Output is correct
9 Correct 33 ms 26052 KB Output is correct
10 Correct 143 ms 27208 KB Output is correct
11 Correct 196 ms 28744 KB Output is correct
12 Correct 326 ms 28744 KB Output is correct
13 Correct 283 ms 28744 KB Output is correct
14 Correct 286 ms 28744 KB Output is correct