#include "elephants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 150000 + 10;
const int INF = 2e9;
int n, len;
int a[MAXN];
std::mt19937 mt(69);
struct Treap
{
struct Node
{
struct Interval
{
int l, r;
friend bool operator < (const Interval &a, const Interval &b)
{
return a.l < b.l;
}
};
int cnt, x, y;
Node *left, *right;
Interval first;
Interval last;
Node()
{
left = right = nullptr;
}
Node (int _x, int _y)
{
x = _x;
y = _y;
cnt = 1;
left = right = nullptr;
first.l = first.r = x;
last = first;
}
};
Node *root;
void recover(Node *curr)
{
if (curr == nullptr)
{
return;
}
curr->cnt = 1;
curr->first = curr->last = {curr->x, curr->x};
if (curr->left != nullptr)
{
if (curr->left->last.l + len >= curr->first.r)
{
if (curr->cnt == 1)
{
curr->last = {curr->left->last.l, curr->first.r};
}
curr->cnt = curr->left->cnt + curr->cnt - 1;
if (curr->left->cnt == 1)
{
curr->first = {curr->left->last.l, curr->first.r};
} else
{
curr->first = curr->left->first;
}
} else
{
curr->cnt = curr->left->cnt + curr->cnt;
curr->first = curr->left->first;
}
}
if (curr->right != nullptr)
{
if (curr->last.l + len >= curr->right->first.r)
{
if (curr->cnt == 1)
{
curr->first = {curr->last.l, curr->right->first.r};
}
curr->cnt = curr->right->cnt + curr->cnt - 1;
if (curr->right->cnt == 1)
{
curr->last = {curr->last.l, curr->right->first.r};
} else
{
curr->last = curr->right->last;
}
} else
{
curr->cnt = curr->right->cnt + curr->cnt;
curr->last = curr->right->last;
}
}
}
void split(Node *curr, Node *&left, Node *&right, int k)
{
if (curr == nullptr)
{
left = right = nullptr;
return;
}
if (curr->x <= k)
{
left = curr;
split(curr->right, left->right, right, k);
recover(left);
} else
{
right = curr;
split(curr->left, left, right->left, k);
recover(right);
}
}
void merge(Node *&curr, Node *left, Node *right)
{
if (left == nullptr)
{
curr = right;
return;
}
if (right == nullptr)
{
curr = left;
return;
}
if (left->y > right->y)
{
curr = left;
merge(curr->right, left->right, right);
} else
{
curr = right;
merge(curr->left, left, right->left);
}
recover(curr);
}
void insert(int x)
{
Node *curr = new Node(x, mt());
Node *left, *right;
split(root, left, right, curr->x);
merge(left, left, curr);
merge(root, left, right);
}
void erase(int x)
{
Node *left, *right, *ll, *lr;
split(root, left, right, x);
split(left, ll, lr, x - 1);
merge(root, ll, right);
}
void printTreap(Node *curr)
{
std::cout << curr->x << ' ' << curr->cnt << ' ' << curr->first.l << ' ' << curr->first.r << ' ' << curr->last.l << ' ' << curr->last.r << '\n';
if (curr->left != nullptr)
{
std::cout << "left of: " << curr->x << '\n';
printTreap(curr->left);
}
if (curr->right != nullptr)
{
std::cout << "right of: " << curr->x << '\n';
printTreap(curr->right);
}
}
void printTreap()
{
std::cout << "root\n";
printTreap(root);
}
};
Treap treap;
std::multiset <int> ms;
void init(int N, int L, int X[])
{
n = N;
len = L;
for (int i = 0 ; i < n ; ++i)
{
a[i + 1] = X[i];
treap.insert(X[i]);
ms.insert(X[i]);
}
}
int update(int idx, int y)
{
a[idx + 1] = y;
std::vector <int> vals;
for (int i = 1 ; i <= n ; ++i)
{
vals.push_back(a[i]);
}
int coveredTo = -1, ans = 0;
std::sort(vals.begin(), vals.end());
for (const int &i : vals)
{
if (coveredTo < i)
{
ans++;
coveredTo = i + len;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
7830 ms |
3396 KB |
Output is correct |
| 8 |
Execution timed out |
9052 ms |
4316 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
7830 ms |
3396 KB |
Output is correct |
| 8 |
Execution timed out |
9052 ms |
4316 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
312 KB |
Output is correct |
| 6 |
Correct |
1 ms |
316 KB |
Output is correct |
| 7 |
Correct |
7830 ms |
3396 KB |
Output is correct |
| 8 |
Execution timed out |
9052 ms |
4316 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
