Submission #594643

#	Time	Username	Problem	Language	Result	Execution time	Memory
594643		penguinhacker	Safety (NOI18_safety)	C++17	100 / 100	439 ms	21724 KiB

safety

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

mt19937 rng(42);

struct Node {
	int sz=1, pri=rng();
	ll val=0, lz=0;
	Node *left=nullptr, *right=nullptr;
	Node(ll x) : val(x) {}
};

int sz(Node* u) {
	return u?u->sz:0;
}

Node* cmb(Node* u) {
	u->sz=1+sz(u->left)+sz(u->right);
	return u;
}

void psh(Node* u) {
	if (u&&u->lz) {
		u->val+=u->lz;
		if (u->left)
			u->left->lz+=u->lz;
		if (u->right)
			u->right->lz+=u->lz;
		u->lz=0;
	}
}

ar<Node*, 2> split1(Node* u, int k) {
	if (!u)
		return {nullptr, nullptr};
	psh(u);
	if (sz(u->left)>=k) {
		ar<Node*, 2> x=split1(u->left, k);
		u->left=x[1];
		return {x[0], cmb(u)};
	} else {
		ar<Node*, 2> x=split1(u->right, k-sz(u->left)-1);
		u->right=x[0];
		return {cmb(u), x[1]};
	}
}

ar<Node*, 2> split2(Node* u, ll k) {
	if (!u)
		return {nullptr, nullptr};
	psh(u);
	if (u->val>k) {
		ar<Node*, 2> x=split2(u->left, k);
		u->left=x[1];
		return {x[0], cmb(u)};
	} else {
		ar<Node*, 2> x=split2(u->right, k);
		u->right=x[0];
		return {cmb(u), x[1]};
	}
}

Node* mrg(Node* u, Node* v) {
	psh(u), psh(v);
	if (!u||!v)
		return u?u:v;
	if (u->pri>v->pri) {
		u->right=mrg(u->right, v);
		return cmb(u);
	} else {
		v->left=mrg(u, v->left);
		return cmb(v);
	}
}

void app(Node* u, ll x) {
	assert(u);
	u->lz+=x;
	psh(u);
}

ll walk(Node* u, int dir) {
	while(1) {
		psh(u);
		Node* nxt=dir==0?u->left:u->right;
		if (nxt)
			u=nxt;
		else
			break;
	}
	return u->val;
}

const int mxN=2e5;
int n, h, a[mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> h;
	for (int i=0; i<n; ++i)
		cin >> a[i];
	ll ans=0;
	Node* rt=mrg(new Node(a[0]), new Node(a[0]));
	for (int i=1; i<n; ++i) {
		ar<Node*, 2> x=split1(rt, i);
		app(x[0], -h);
		app(x[1], h);
		ll bound=walk(x[0], 1);
		if (a[i]<bound)
			ans+=bound-a[i];
		else {
			bound=walk(x[1], 0);
			if (a[i]>bound)
				ans+=a[i]-bound;
		}
		rt=mrg(x[0], x[1]);
		x=split2(rt, a[i]);
		rt=mrg(mrg(x[0], new Node(a[i])), mrg(new Node(a[i]), x[1]));
	}
	cout << ans;
	return 0;
}

• 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