oj.uz

Submission #95237

# Submission time Handle Problem Language Result Execution time Memory
95237 2019-01-28T22:49:20 Z shoemakerjo Pinball (JOI14_pinball) C++14
100 / 100
 861 ms 200028 KB 
#include <bits/stdc++.h>

using namespace std;

int M, N; //N is up to 10^9 
const int maxm = 100010;
using ll = long long;

int a[maxm];
int b[maxm];
int c[maxm];
ll d[maxm];
const ll inf = 1e18;

//let's just do dynamic

struct node {
	ll val;
	node *left;
	node *right;
	node (ll vv, node *ll, node *rr) :
		val(vv), left(ll),  right(rr) {}
	node *insert(int spot, ll val, int ss, int se);
};

node *null = new node(inf, NULL, NULL);

node *leftroot;
node *rightroot;

node *node::insert(int spot, ll val, int ss , int se) {
	if (ss == se) {
		return new node(min(this->val, val), null, null);
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		return new node(min(this->val, val),
			this->left->insert(spot, val, ss, mid),
			this->right);
	}
	return new node(min(this->val, val),
		this->left, 
		this->right->insert(spot, val, mid+1, se));
}

ll query(node *cur, int qs, int qe, int ss = 1, int se = N) {
	if (qs > qe || ss > se || qs > se || qe < ss) return inf;
	if (qs <= ss && se <= qe) return cur->val;
	int mid = (ss+se)/2;
	return min(query(cur->left, qs, qe, ss, mid),
		query(cur->right, qs, qe, mid+1, se));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	null->right = null;
	null->left = null;
	//1 device for each row
	cin >> M >> N;
	for (int i = 1; i <= M; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	leftroot = new node(inf, null, null);
	rightroot = new node(inf, null, null);

	leftroot = leftroot->insert(1, 0, 1, N);
	rightroot = rightroot->insert(N, 0, 1, N);

	ll ans = inf;
	for (int i = 1; i <= M; i++) {
		ll cl; //get to my left endpoint
		ll cr; //get to my right endpoint

		cl = query(leftroot, a[i], N);
		cr = query(rightroot, 1, b[i]);

		ans = min(ans, cl + cr + d[i]);

		// cout << "updating " << c[i] << " : " << 
		// 	cl+d[i] << " - " << cr + d[i] << endl;

		leftroot = leftroot->insert(c[i], cl + d[i], 1, N);
		rightroot = rightroot->insert(c[i], cr + d[i], 1, N);
	}
	if (ans >= inf) cout << -1 << endl;
	else cout << ans << endl;

}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 6 ms 2424 KB Output is correct
18 Correct 6 ms 2316 KB Output is correct
19 Correct 6 ms 2296 KB Output is correct
20 Correct 7 ms 2296 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 6 ms 2168 KB Output is correct
23 Correct 6 ms 2296 KB Output is correct
24 Correct 6 ms 2424 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 632 KB Output is correct
10 Correct 2 ms 632 KB Output is correct
11 Correct 3 ms 760 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct
14 Correct 3 ms 760 KB Output is correct
15 Correct 2 ms 504 KB Output is correct
16 Correct 3 ms 760 KB Output is correct
17 Correct 6 ms 2424 KB Output is correct
18 Correct 6 ms 2316 KB Output is correct
19 Correct 6 ms 2296 KB Output is correct
20 Correct 7 ms 2296 KB Output is correct
21 Correct 3 ms 1016 KB Output is correct
22 Correct 6 ms 2168 KB Output is correct
23 Correct 6 ms 2296 KB Output is correct
24 Correct 6 ms 2424 KB Output is correct
25 Correct 38 ms 13932 KB Output is correct
26 Correct 117 ms 42540 KB Output is correct
27 Correct 401 ms 125432 KB Output is correct
28 Correct 443 ms 189120 KB Output is correct
29 Correct 311 ms 96980 KB Output is correct
30 Correct 861 ms 199912 KB Output is correct
31 Correct 676 ms 199928 KB Output is correct
32 Correct 686 ms 199984 KB Output is correct
33 Correct 70 ms 31836 KB Output is correct
34 Correct 267 ms 97016 KB Output is correct
35 Correct 463 ms 200016 KB Output is correct
36 Correct 634 ms 199800 KB Output is correct
37 Correct 633 ms 200028 KB Output is correct
38 Correct 582 ms 199816 KB Output is correct