#include <bits/stdc++.h>
#include "elephants.h"
//#include "Lgrader.cpp"
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
const int inf = (int)2e9 + 42;
random_device rd;
mt19937 mt(rd());
struct node
{
int sum, val, sz, prior;
node *l, *r, *par, *pp;
node() { l = r = par = pp = nullptr; sum = val = sz = prior = 0; }
node(int v) { l = r = par = pp = nullptr; sum = val = v; sz = 1; prior = mt(); }
};
using pnode = node*;
pnode get_l(pnode t) { while(t->l) t = t->l; return t; }
pnode get_r(pnode t) { while(t->r) t = t->r; return t; }
pnode get_par(pnode t) { while(t->par) t = t->par; return t; }
inline int size(pnode t) { return t ? t->sz : 0; }
inline int sum(pnode t) { return t ? t->sum : 0; }
void pull(pnode &t)
{
if(!t) return;
t->sz = size(t->l) + size(t->r) + 1;
t->sum = t->val + sum(t->l) + sum(t->r);
t->par = nullptr;
if(t->l) t->l->par = t;
if(t->r) t->r->par = t;
if(t->l && t->l->pp) t->pp = t->l->pp, t->l->pp = nullptr;
if(t->r && t->r->pp) t->pp = t->r->pp, t->r->pp = nullptr;
}
void merge(pnode &t, pnode l, pnode r)
{
if(!l) { t = r; pull(t); return; }
if(!r) { t = l; pull(t); return; }
if(l->prior > r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
pull(t);
}
void split(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
if(!t) { l = nullptr; r = nullptr; return; }
int idx = add + size(t->l);
if(idx <= k)
split(t->r, t->r, r, k, idx + 1), l = t;
else
split(t->l, l, t->l, k, add), r = t;
pull(t);
}
pnode remove_left(pnode u)
{
int pos = size(u->l);
pnode root = u;
while(root->par)
{
if(root->par->r == root) pos += size(root->par->l) + 1;
root = root->par;
}
pnode L, R;
split(root, L, R, pos - 1);
return R;
}
pnode remove_right(pnode u)
{
int pos = size(u->l);
pnode root = u;
while(root->par)
{
if(root->par->r == root) pos += size(root->par->l) + 1;
root = root->par;
}
pnode L, R, prv_pp = root->pp;
root->pp = nullptr;
split(root, L, R, pos);
if(R) R->pp = u;
L->pp = prv_pp;
return L;
}
pnode merge_trees(pnode l, pnode r)
{
pnode rt;
if(r) r->pp = nullptr;
merge(rt, l, r);
return rt;
}
struct link_cut_tree
{
pnode tr[MAXN];
void new_node(int i, int col) { tr[i] = new node(col); }
pnode access(pnode u)
{
u = remove_right(u);
while(u->pp)
{
pnode p = remove_right(u->pp);
u = merge_trees(p, u);
}
return u;
}
int query(pnode u)
{
u = access(u);
return sum(u);
}
void cut(pnode u)
{
access(u);
remove_left(u);
}
void link(pnode w, pnode u)
{
w = access(w);
u = access(u);
merge_trees(u, w);
}
};
link_cut_tree lct;
int n, L;
int x[MAXN];
set<pair<int, int> > st;
void update_link(set<pair<int, int> >::iterator it)
{
pnode p, u = lct.tr[it->second];
lct.cut(u);
if(it->second != 2 * n && (it->second & 1) == 0) p = lct.tr[it->second + 1];
else p = lct.tr[next(it)->second];
lct.link(u, p);
}
void init(int N, int L, int X[])
{
n = N;
L++;
::L = L;
lct.new_node(2 * N, 0);
lct.new_node(2 * N + 1, 0);
st.insert({-42, 2 * N});
st.insert({inf, 2 * N + 1});
for(int i = 0; i < N; i++)
{
lct.new_node(2 * i, 1);
lct.new_node(2 * i + 1, 0);
lct.link(lct.tr[2 * i], lct.tr[2 * i + 1]);
st.insert({X[i], 2 * i});
st.insert({X[i] + L, 2 * i + 1});
x[i] = X[i];
}
for(auto it = st.begin(); it != prev(st.end()); ++it)
update_link(it);
}
void cut(int i) { lct.cut(lct.tr[i]); }
int update(int i, int y)
{
auto it1 = st.lower_bound({x[i], 2 * i});
auto it2 = st.lower_bound({x[i] + L, 2 * i + 1});
cut(it1->second);
cut(it2->second);
auto f = prev(it1), s = prev(it2);
cut(prev(it1)->second);
cut(prev(it2)->second);
st.erase(it1);
st.erase(it2);
x[i] = y;
it1 = st.insert({x[i], 2 * i}).first;
it2 = st.insert({x[i] + L, 2 * i + 1}).first;
update_link(f);
update_link(s);
update_link(it1);
update_link(it2);
update_link(prev(it1));
update_link(prev(it2));
return lct.query(lct.tr[2 * n]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
616 KB |
Output is correct |
| 3 |
Correct |
3 ms |
616 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
732 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
