#include <bits/stdc++.h>
#define int long long
using namespace std;
using Point = pair<int, int>;
using idata = vector<int>;
struct Node {
int pos, delta, rng;
int ssize = 1;
int sdelt = 0;
Node* left; Node* right;
void compute () {
ssize = 1;
sdelt = delta;
if (left != nullptr) {
ssize += left->ssize;
sdelt += left->sdelt;
}
if (right != nullptr) {
ssize += right->ssize;
sdelt += right->sdelt;
}
}
};
struct Treap {
Node* root;
static void __show (Node* node, int depth) {
if (node == nullptr) {
for (int i = 0; i < depth; i ++) cout << " ";
cout << ">\n";
return ;
}
for (int i = 0; i < depth; i ++) cout << " ";
cout << "> " << node->pos << " " << node->delta << endl;
__show(node->left, depth + 1);
__show(node->right, depth + 1);
}
void show () {
__show(root, 0);
}
static Node* __merge (Node* A, Node* B) {
if (A == nullptr) return B;
if (B == nullptr) return A;
if (A->rng >= B->rng) {
A->right = __merge(A->right, B);
A->compute();
return A;
} else {
B->left = __merge(A, B->left);
B->compute();
return B;
}
}
static pair<Node*, Node*> __split (Node* A, int k) {
if (A == nullptr) return { nullptr, nullptr };
if (A->pos > k) {
const auto [LL, LR] = __split(A->left, k);
A->left = LR;
A->compute();
return { LL, A };
} else {
const auto [RL, RR] = __split(A->right, k);
A->right = RL;
A->compute();
return { A, RR };
}
}
void insert( int pos, int delta ) {
Node* node = new Node();
node->pos = pos;
node->delta = delta;
node->rng = rand();
node->sdelt = delta;
const auto ldata = __split(root, pos - 1);
Node* left = ldata.first;
const auto rdata = __split(ldata.second, pos);
Node* right = rdata.second;
Node* mid = rdata.first;
if (mid == nullptr) mid = node;
else {
delete node;
mid->delta += delta;
mid->sdelt += delta;
}
root = __merge(left, __merge(mid, right));
}
int query (int x) {
Node* local = root;
int res = 0;
while (local != nullptr) {
if (local->pos > x) local = local->left;
else {
res += local->delta;
if (local->left != nullptr) res += local->left->sdelt;
local = local->right;
}
}
return res;
}
void __chmin (Node* node, int until) {
if (node == nullptr) return ;
if (node->left != nullptr) {
if (node->left->sdelt > until) {
__chmin(node->left, until);
node->right = nullptr;
node->delta = 0;
node->compute();
return ;
} else until -= node->left->sdelt;
}
if (until < node->delta) {
node->delta = until;
node->right = nullptr;
node->compute();
return ;
}
until -= node->delta;
__chmin(node->right, until);
}
void chmin (int until) {
__chmin(root, until);
}
Treap cut (int position) {
const auto data = __split(root, position);
root = data.first;
Treap other; other.root = data.second;
return other;
}
static void __traverse (Node* node, vector<Node*> &answer) {
if (node == nullptr) return ;
answer.push_back(node);
__traverse(node->left, answer);
__traverse(node->right, answer);
}
vector<Node*> traverse () {
vector<Node*> ans;
__traverse(root, ans);
return ans;
}
int size () { return root != nullptr ? root->ssize : 0; }
void swap (Treap &other) {
Node* c = root;
root = other.root;
other.root = c;
}
};
void compile (Treap &treap, int H_i, int C_i) {
int chmin_left = treap.query( H_i );
Treap right = treap.cut(H_i);
right.insert( H_i + 1, C_i );
treap.insert( - 1e9, C_i );
treap.chmin( chmin_left );
treap.root = treap.__merge(treap.root, right.root);
}
void merge (Treap &target, Treap &other) {
if (target.size() < other.size())
target.swap(other);
for (Node* node : other.traverse())
target.insert(node->pos, node->delta);
}
vector<Treap> treapArray;
idata A, H, C;
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
treapArray.resize(N);
A.resize(N); H.resize(N); C.resize(N);
for (int i = 0; i < N; i ++) {
cin >> A[i] >> H[i] >> C[i];
A[i] --;
if ((i != 0 && A[i] > i - 1) || (i == 0 && A[i] != 0)) return 0;
}
for (int i = N - 1; i >= 0; i --) {
compile(treapArray[i], H[i], C[i]);
if (i == 0) continue ;
merge(treapArray[A[i]], treapArray[i]);
}
cout << treapArray[0].query(1) << endl;
}
Compilation message
worst_reporter2.cpp: In static member function 'static std::pair<Node*, Node*> Treap::__split(Node*, long long int)':
worst_reporter2.cpp:68:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | const auto [LL, LR] = __split(A->left, k);
| ^
worst_reporter2.cpp:74:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | const auto [RL, RR] = __split(A->right, k);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
212 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
2036 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
212 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
2036 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
212 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
2036 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
