#include <bits/stdc++.h>
#ifndef LOCAL
#include "elephants.h"
#endif
const int32_t MAX_N = 150000;
const int32_t INF = 2e9;
const int32_t OFFSET = 1e6;
std::mt19937 mt(69);
struct Node {
bool rev;
int32_t sz, val, sum, prior;
Node *l, *r, *par, *pp;
Node() {}
Node(int32_t _val) : val(_val), sum(_val) {
rev = false;
sz = 1;
prior = mt();
l = nullptr;
r = nullptr;
par = nullptr;
pp = nullptr;
}
static int32_t get_size(Node *x) {
return (x ? x->sz : 0);
}
static int32_t get_sum(Node *x) {
return (x ? x->sum : 0);
}
static void push_lazy(Node *x) {
if(!x) {
return;
}
if(x->rev) {
std::swap(x->l, x->r);
if(x->l) {
x->l->rev ^= 1;
}
if(x->r) {
x->r->rev ^= 1;
}
x->rev = false;
}
}
static void recalc(Node *x) {
if(!x) {
return;
}
push_lazy(x);
x->sz = get_size(x->l) + get_size(x->r) + 1;
x->sum = get_sum(x->l) + get_sum(x->r) + x->val;
x->par = nullptr;
if(x->l) {
x->l->par = x;
if(x->l->pp) {
x->pp = x->l->pp;
x->l->pp = nullptr;
}
}
if(x->r) {
x->r->par = x;
if(x->r->pp) {
x->pp = x->r->pp;
x->r->pp = nullptr;
}
}
}
static Node* merge(Node *x, Node *y) {
push_lazy(x);
push_lazy(y);
if(!x) {
return y;
}
if(!y) {
return x;
}
if(x->prior > y->prior) {
x->r = merge(x->r, y);
recalc(x);
return x;
}
else {
y->l = merge(x, y->l);
recalc(y);
return y;
}
}
static std::pair< Node*, Node* > split(Node *x, int32_t key, int32_t add = 0) {
push_lazy(x);
if(!x) {
return { nullptr, nullptr };
}
int32_t currKey = add + get_size(x->l);
if(currKey <= key) {
auto aux = split(x->r, key, currKey + 1);
x->r = aux.first;
recalc(x);
return { x, aux.second };
}
else {
auto aux = split(x->l, key, add);
x->l = aux.second;
recalc(x);
return { aux.first, x };
}
}
static int32_t get_pos(Node *x) {
int32_t pos = get_size(x->l);
while(x->par) {
if(x->rev) {
pos = get_size(x) - pos - 1;
}
if(x->par->r == x) {
pos += get_size(x->par->l) + 1;
}
x = x->par;
}
if(x->rev) {
pos = get_size(x) - pos - 1;
}
return pos;
}
static Node* get_root(Node *x) {
while(x->par) {
x = x->par;
}
return x;
}
static Node* split_after(Node *x) {
int32_t pos = get_pos(x);
Node *root = get_root(x);
Node *pp = root->pp;
root->pp = nullptr;
auto aux = split(root, pos);
if(aux.second) {
aux.second->pp = x;
}
root = aux.first;
root->pp = pp;
return root;
}
static Node* access(Node *x) {
x = split_after(x);
while(x->pp) {
Node *u = x->pp;
u = split_after(u);
x->pp = nullptr;
x = merge(u, x);
}
return x;
}
static void reroot(Node *x) {
x = access(x);
x->rev ^= 1;
}
static void link(Node *x, Node *y) {
reroot(x);
x->pp = y;
}
static void cut(Node *x) {
Node *u = access(x);
split(u, get_size(u) - 2);
}
};
int32_t n, l, x[MAX_N + 5];
std::set< std::pair< int32_t, int32_t > > s;
Node *nodes[2 * MAX_N + 5];
int32_t answer_query() {
Node *u = Node::access(nodes[2 * n]);
return Node::get_sum(u);
}
void init(int32_t _n, int32_t _l, int32_t *_x) {
n = _n;
l = _l;
for(int32_t i = 0; i < n; i++) {
x[i] = _x[i];
s.insert({ x[i], 2 * i });
s.insert({ x[i] + l, 2 * i + 1 + OFFSET });
nodes[2 * i] = new Node(1);
nodes[2 * i + 1] = new Node(0);
}
s.insert({ -1, 2 * n });
s.insert({ INF, 2 * n + 1 + OFFSET });
nodes[2 * n] = new Node(0);
nodes[2 * n + 1] = new Node(0);
for(int32_t i = 0; i < n; i++) {
Node::link(nodes[2 * i], nodes[2 * i + 1]);
auto it = s.lower_bound({ x[i] + l, 2 * i + 2 + OFFSET })->second;
Node::link(nodes[2 * i + 1], nodes[it]);
}
auto it = s.lower_bound({ 0, -1 })->second;
Node::link(nodes[2 * n], nodes[it]);
}
int32_t get_right_ind(int32_t p) {
return (p > OFFSET ? p - OFFSET : p);
}
void fix_link(std::set< std::pair< int32_t, int32_t > >::iterator it) {
Node *u, *v = nodes[get_right_ind(it->second)];
Node::cut(v);
if(get_right_ind(it->second) != 2 * n && get_right_ind(it->second) % 2 == 0) {
u = nodes[get_right_ind(it->second) + 1];
}
else {
u = nodes[get_right_ind(next(it)->second)];
}
Node::link(v, u);
}
int32_t update(int32_t i, int32_t y) {
auto it1 = s.lower_bound({ x[i], 2 * i });
auto it2 = s.lower_bound({ x[i] + l, 2 * i + 1 + OFFSET });
Node::cut(nodes[get_right_ind(it1->second)]);
Node::cut(nodes[get_right_ind(it2->second)]);
auto aux1 = prev(it1), aux2 = prev(it2);
Node::cut(nodes[get_right_ind(prev(it1)->second)]);
Node::cut(nodes[get_right_ind(prev(it2)->second)]);
s.erase(it1);
s.erase(it2);
x[i] = y;
it1 = s.insert({ y, 2 * i }).first;
it2 = s.insert({ y + l, 2 * i + 1 + OFFSET }).first;
fix_link(aux1);
fix_link(aux2);
fix_link(it1);
fix_link(it2);
fix_link(prev(it1));
fix_link(prev(it2));
return answer_query();
}
#ifdef LOCAL
#include "grader.cpp"
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
