oj.uz

Submission #405740

# Submission time Handle Problem Language Result Execution time Memory
405740 2021-05-16T21:02:34 Z ritul_kr_singh Pinball (JOI14_pinball) C++17
11 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e16;

struct SegmentTree{
	vector<int> a; int sz = 1;
	SegmentTree(int n){
		while(sz < n) sz += sz;
		a.assign(2*sz, INF);
	}
	void update(int i, int v, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = min(a[x], v));
		int mx = (lx + rx) / 2;
		if(i < mx) update(i, v, 2*x+1, lx, mx);
		else update(i, v, 2*x+2, mx, rx);
		a[x] = min(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v){ update(i, v, 0, 0, sz); }
	int rangeMin(int l, int r, int x, int lx, int rx){
		if(r<=lx || rx<=l) return INF;
		if(l<=lx && rx<=r) return a[x];
		int mx = (lx + rx) / 2;
		return min(rangeMin(l, r, 2*x+1, lx, mx), rangeMin(l, r, 2*x+2, mx, rx));
	}
	int rangeMin(int l, int r){ return rangeMin(l, r+1, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int m, n; cin >> m >> n;
	array<int, 4> a[m];
	vector<int> vals = {1, n};
	for(auto &i : a){
		for(int j=0; j<3; ++j) cin >> i[j], vals.push_back(i[j]);
		cin >> i[3];
	}

	sort(vals.begin(), vals.end());
	for(auto &i : a){
		for(int j=0; j<3; ++j) i[j] = lower_bound(vals.begin(), vals.end(), i[j]) - vals.begin();
	}

	int last = lower_bound(vals.begin(), vals.end(), n) - vals.begin();

	SegmentTree dpL(last+1), dpR(last+1);
	dpL.update(0, 0);
	dpR.update(last, 0);

	int res = INF;
	
	for(auto &i : a){
		int l = dpL.rangeMin(i[0], i[2]);
		int r = dpR.rangeMin(i[2], i[1]);
		res = min(res, l + r + i[3]);

		dpL.update(i[2], l + i[3]);
		dpR.update(i[2], r + i[3]);
	}

	cout << (res == INF ? -1 : res);
}

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 1 ms 332 KB Output isn't correct
12 Halted 0 ms 0 KB -