Submission #701709

#	Time	Username	Problem	Language	Result	Execution time	Memory
701709		GusterGoose27	Safety (NOI18_safety)	C++11	100 / 100	401 ms	36560 KiB

safety

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

const int MAXN = 2e5;
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 / 3
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 5 / 5
• Subtask 5: 6 / 6
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 22 / 22
• Subtask 9: 29 / 29