oj.uz

Submission #1033286

# Submission time Handle Problem Language Result Execution time Memory
1033286 2024-07-24T16:02:22 Z zaza Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 604 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Seg{
	
	int n;
	
	vector<long long> s;
	
	Seg(int _n = 0): n(_n) {
		s.resize(4 << __lg(n), 2e18);
	}
	
	void upd(int i, long long v) {
		
		int l = 1, r = n, id = 1;
		
		while (l < r) {
			int mid = (l + r) / 2;
			id *= 2;
			
			if (i <= mid) {
				r = mid;
			} else {
				l = mid + 1;
				id++;
			}
			
		}
		
		s[id] = min(s[id], v);
		
		while (id > 1) {
			id /= 2;	
			s[id] = min(s[id * 2], s[id * 2 + 1]);
		}
	}
	
	long long get(int i, int j, int id, int l, int r) {
		
		if (i <= l && r <= j) {
			return s[id];
		}
		
		int mid = (l + r) / 2;
		
		if (i <= mid && mid < j) {
			return min(get(i, j, id * 2, l, mid), get(i, j, id * 2 + 1, mid + 1, r));
		}
		
		if (mid < i) {
			return get(i, j, id * 2 + 1, mid + 1, r);
		}
		
		return get(i, j, id * 2, l, mid);		
	}
	
	long long get(int i, int j) {
		return get(i, j, 1, 1, n);
	}
};

int m, n;

int a[100005], b[100005], c[100005], d[100005];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> m >> n;
	
	vector<int> val;
	
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		
		val.emplace_back(a[i]);
		val.emplace_back(b[i]);
		val.emplace_back(c[i]);
	}
	
	sort(val.begin(), val.end());
	
	val.erase(unique(val.begin(), val.end()), val.end());
	
	for (int i = 1; i <= m; ++i) {
		a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
		b[i] = lower_bound(val.begin(), val.end(), b[i]) - val.begin() + 1;
		c[i] = lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1;
		
		//cout << a[i] << ' ' << b[i] << ' ' << c[i] << '\n';
	}
	
	int t = val.size();
	
	Seg ST1(t), ST2(t);
	
	long long ans = 2e18;
	
	ST1.upd(1, 0);
	ST2.upd(t, 0);
	
	for (int i = 1; i <= m; ++i) {
		
		long long k1 = ST1.get(a[i], b[i]);
		long long k2 = ST2.get(a[i], b[i]);
		
		if (max(k1, k2) < 2e18) {
			ans = min(ans, k1 + k2 + d[i]);
		}
		
		if (k1 < 2e18) {
			ST1.upd(c[i], k1 + d[i]);
		}
		
		if (k2 < 2e18) {
			ST2.upd(c[i], k2 + d[i]);
		}
	}
	
	if (ans < 2e18) {
		cout << ans << '\n';
	} else {
		cout << "-1\n";
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 604 KB Output isn't correct
8 Halted 0 ms 0 KB -