oj.uz

Submission #701706

# Submission time Handle Problem Language Result Execution time Memory
701706 2023-02-22T01:57:32 Z GusterGoose27 Safety (NOI18_safety) C++17
66 / 100
 11 ms 3204 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = 1e5;
const int inf = 2e9;
int n, h;
int heights[MAXN];
mt19937 gen(0);

pii operator+(pii a, pii b) {
	return pii(a.first+b.first, a.second+b.second);
}

class Node;

class Node {
public:
	Node *l = nullptr;
	Node *r = nullptr;
	unsigned int key;
	pii val; //
	pii sum;
	Node(pii v) : val(v) {
		key = gen();
		sum = val;
	}
	static pii get_val(Node *rt) {
		return (rt == nullptr) ? pii(0, 0) : rt->val;
	}
	static pii get_sum(Node *rt) {
		return (rt == nullptr) ? pii(0, 0) : rt->sum;
	}
	void make_sum() {
		sum = val+get_sum(l)+get_sum(r);
	}
	void make_inorder(vector<pii> &res) {
		if (l) l->make_inorder(res);
		res.push_back(val);
		if (r) r->make_inorder(res);
	}
};

void merge(Node *l, Node *r, Node *&rt) {
	if (l == nullptr) {
		rt = r;
		return;
	}
	if (r == nullptr) {
		rt = l;
		return;
	}
	if (l->key < r->key) {
		rt = l;
		merge(l->r, r, l->r);
		return rt->make_sum();
	}
	rt = r;
	merge(l, r->l, r->l);
	rt->make_sum();
}

void split(Node *rt, Node *&l, Node *&r, int v) { // split by x-value, for adding a new line
	int amt = Node::get_sum(rt->l).second;
	if (amt > v) {
		r = rt;
		split(rt->l, l, r->l, v);
		return r->make_sum();
	}
	if (amt+rt->val.second < v) {
		l = rt;
		split(rt->r, l->r, r, v-amt-rt->val.second);
		return l->make_sum();
	}
	r = rt->r;
	l = rt;
	l->r = nullptr;
	return l->make_sum();
}

void split2(Node *rt, Node *&l, Node *&r, int v) { // split by slope, for expanding
	int amt = Node::get_sum(rt->l).first;
	if (amt > v) {
		r = rt;
		split2(rt->l, l, r->l, v);
		return r->make_sum();
	}
	if (amt+rt->val.first < v) {
		l = rt;
		split2(rt->r, l->r, r, v-amt-rt->val.first);
		return l->make_sum();
	}
	l = rt->l;
	r = rt;
	r->l = nullptr;
	return r->make_sum();
}

int get_r_dist(Node *rt) {
	if (rt->r != nullptr) return get_r_dist(rt->r);
	return rt->val.second;
}

void set_r_dist(Node *rt, int v) {
	if (rt->r != nullptr) set_r_dist(rt->r, v);
	else rt->val.second = v;
	rt->make_sum();
}

void sub_l_slope(Node *rt, int v) {
	if (rt->l != nullptr) sub_l_slope(rt->l, v);
	else rt->val.first -= v;
	rt->make_sum();
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> h;
	for (int i = 0; i < n; i++) cin >> heights[i];
	Node *tree = new Node(pii(0, inf));
	int lzx = 0; // + amount by which tree is supposed to be left shifted
	int init_slope = 0; // + initial slope
	int y = 0;
	for (int i = n-1; i >= 0; i--) {
		Node *l;
		Node *r;
		split(tree, l, r, heights[i]+lzx);
		y += heights[i]+lzx;
		int rdist = Node::get_sum(l).second-heights[i]-lzx;
		int ldist = get_r_dist(l)-rdist;
		set_r_dist(l, ldist);
		Node *mid = new Node(pii(2, rdist));
		init_slope++;
		merge(l, mid, l);
		merge(l, r, tree);
		split2(tree, l, r, init_slope);
		int ex_slope = init_slope-Node::get_sum(l).first;
		sub_l_slope(r, ex_slope);
		mid = new Node(pii(ex_slope, 2*h));
		lzx += h;
		merge(l, mid, l);
		merge(l, r, tree);
	}
	Node *l;
	Node *r;
	split2(tree, l, r, init_slope);
	vector<pii> inorder;
	l->make_inorder(inorder);
	for (pii p: inorder) {
		init_slope -= p.first;
		y -= init_slope*p.second;
	}
	cout << y << "\n";
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct

Subtask #2
4.0 / 4.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 3204 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 5 ms 1164 KB Output is correct
29 Correct 4 ms 1108 KB Output is correct
30 Correct 5 ms 1156 KB Output is correct
31 Correct 4 ms 984 KB Output is correct
32 Correct 5 ms 1040 KB Output is correct
33 Correct 6 ms 1236 KB Output is correct
34 Correct 6 ms 1108 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 232 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 5 ms 1164 KB Output is correct
35 Correct 4 ms 1108 KB Output is correct
36 Correct 5 ms 1156 KB Output is correct
37 Correct 4 ms 984 KB Output is correct
38 Correct 5 ms 1040 KB Output is correct
39 Correct 6 ms 1236 KB Output is correct
40 Correct 6 ms 1108 KB Output is correct
41 Correct 5 ms 1236 KB Output is correct
42 Correct 4 ms 896 KB Output is correct
43 Correct 5 ms 1104 KB Output is correct
44 Correct 5 ms 1248 KB Output is correct
45 Correct 5 ms 1100 KB Output is correct
46 Correct 4 ms 1108 KB Output is correct

Subtask #9
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 224 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 1 ms 232 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Runtime error 11 ms 3204 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -