#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int MAXN = 150005;
/// link-cut node
struct node
{
node *l, *r, *p;
int val, sum, psh;
int ind;
node()
{
l = r = p = 0;
val = sum = 0;
psh = -1;
}
node(int vl)
{
l = r = p = 0;
val = sum = vl;
psh = -1;
}
};
inline void Set(node *v, int val)
{
if(!v) return;
v->psh = v->val = val;
}
inline void push(node *v)
{
if(!v)
return;
if(v->psh != -1)
{
Set(v->l, v->psh);
Set(v->r, v->psh);
v->psh = -1;
}
}
inline int get(node *v)
{
if(!v) return 0;
return v->sum;
}
inline void upd(node *v)
{
if(!v) return;
push(v);
v->sum = get(v->l) + v->val + get(v->r);
}
inline bool is_root(node *v)
{
if(!v) return 0;
if(!v->p) return 1;
return (v->p->l != v) && (v->p->r != v);
}
vector<node*> lct;
inline void Init(int n)
{
lct = vector<node*>(n);
for(int i = 0; i < n; i++)
{
lct[i] = new node(1);
lct[i]->ind = i;
}
}
inline node* new_node(int val)
{
node *nw = new node(val);
lct.push_back(nw);
return nw;
}
inline void rot(node *v)
{
if(!v || is_root(v)) return;
node *p = v->p;
push(p);
push(v);
if(!is_root(p))
{
node *g = p->p;
if(g->l == p) g->l = v;
else g->r = v;
}
if(p->l == v)
{
p->l = v->r;
if(p->l) p->l->p = p;
v->r = p;
}
else
{
p->r = v->l;
if(p->r) p->r->p = p;
v->l = p;
}
v->p = p->p;
p->p = v;
upd(p);
upd(v);
}
inline void splay(node *v)
{
if(!v) return;
while(!is_root(v))
{
node *p = v->p;
node *g = p->p;
if(!is_root(p))
{
if((g->l == p) == (p->l == v)) rot(p);
else rot(v);
}
rot(v);
}
push(v);
}
inline void access(int i)
{
node *v = lct[i], *c = v, *lst = 0;
while(c)
{
splay(c);
c->r = lst;
upd(c);
lst = c;
c = c->p;
}
splay(v);
}
inline void link(int a, int b)
{
// cout << "link " << a << ' ' << b << '\n';
access(a);
access(b);
node *u = lct[a], *v = lct[b];
u->p = v;
}
inline void cut(int a)
{
// cout << "cut " << a << '\n';
access(a);
node *v = lct[a];
if(v->l)
{
v->l->p = 0;
v->l = 0;
upd(v);
}
}
inline int get_sum(int a)
{
access(a);
node *v = lct[a];
return get(v->l);
}
int len, n;
set<pair<int, int> > st;
int pos[MAXN];
int rc[MAXN], lc[MAXN];
vector<node*> spl;
inline int get_next(int i)
{
if(i == -1)
return -1;
node *v = spl[i];
splay(v);
return v->val;
}
inline node* find_right(node *v)
{
while(v->r)
v = v->r;
return v;
}
inline node* find_left(node *v)
{
while(v->l)
v = v->l;
return v;
}
inline void insert(int i, int l)
{
if(l == -1)
{
node *u = spl[n-1];
splay(u);
node *v = spl[i];
u->l = v;
v->p = u;
// cout << "special insert " << i << ' ' << l << endl;
return;
}
node *u = spl[l], *v = spl[i];
splay(u);
if(u->r)
{
v->r = u->r;
u->r->p = v;
}
u->r = v;
v->p = u;
// cout << "insert " << i << ' ' << l << endl;
}
inline void rem(int i)
{
node *v = spl[i];
splay(v);
node *r = v->r;
if(v->l)
{
v->l->p = 0;
node *l = find_right(v->l);
splay(l);
l->r = r;
if(r)
r->p = l;
}
else
{
if(r)
r->p = 0;
}
v->l = v->r = v->p = 0;
v->sum = v->val = 0;
}
inline void set_next(int l, int r, int val)
{
node *u = spl[l], *v = spl[r];
splay(u);
node *lc = u->l;
if(lc)
{
u->l = 0;
lc->p = 0;
}
splay(v);
v->val = val;
Set(v->l, val);
splay(u);
u->l = lc;
if(u->l)
u->l->p = 0;
}
inline void init_splay(int n)
{
spl = vector<node*>(n);
for(int i = 0; i < n; i++)
{
spl[i] = new node();
}
}
inline void connect(int i)
{
auto it = st.lower_bound({pos[i], i});
int l = -1, r = -1;
if(it != st.begin())
{
auto pr = it; pr--;
l = pr->se;
rc[l] = i;
}
auto nx = it; nx++;
if(nx == st.end())
{
lc[i] = rc[i] = -1;
set_next(i, i, -1);
return;
}
r = nx->se;
lc[r] = i;
lc[i] = l; rc[i] = r;
// cout << i << " left: " << l << " right: " << r << endl;
insert(i, l);
if(l != -1)
{
if(get_next(l) == get_next(r))
{
cut(n+l);
}
}
auto cn = st.lower_bound({pos[i]+len+1, -1});
set_next(i, i, cn->se);
if(get_next(r) == get_next(i))
{
link(i+n, r+n);
}
else
{
link(i+n, get_next(i));
}
if(get_next(l) == get_next(i))
{
if(get_next(l) != get_next(r))
cut(l+n);
link(l+n, i+n);
}
}
inline void disconnect(int i)
{
cut(i+n);
if(lc[i] != -1 && get_next(i) == get_next(lc[i]))
{
cut(lc[i]+n);
if(get_next(lc[i]) == get_next(rc[i]))
{
// cout << "same" << endl;
link(lc[i]+n, rc[i]+n);
}
else
{
// cout << "diff" << endl;
link(lc[i]+n, get_next(lc[i]));
}
}
if(lc[i] != -1)
rc[lc[i]] = -1;
lc[rc[i]] = -1;
}
inline void segment_add(int i)
{
int lp = 0, rp = pos[i]-len-1;
if(lc[i] != -1)
{
lp = pos[lc[i]]-len;
}
// cout << "add " << lp << ' ' << rp << '\n';
auto li = st.lower_bound({lp, -1});
auto ri = st.lower_bound({rp, -1});
if(ri == st.begin())
return;
ri--;
if(li->fi > ri->fi)
return;
int l = li->se, r = ri->se;
// cout << "add idx " << l << ' ' << r << '\n';
if(lc[l] != -1 && get_next(lc[l]) == get_next(l))
{
cut(lc[l]+n);
link(lc[l]+n, get_next(lc[l]));
}
cut(r+n);
link(r+n, i);
set_next(l, r, i);
}
inline void segment_rem(int i)
{
int lp = 0, rp = pos[i]-len-1;
if(lc[i] != -1)
{
lp = pos[lc[i]]-len;
}
auto li = st.lower_bound({lp, -1});
auto ri = st.lower_bound({rp, -1});
if(ri == st.begin())
return;
ri--;
if(li->fi > ri->fi)
return;
int l = li->se, r = ri->se;
cut(r+n);
if(rc[r] != -1 && get_next(rc[r]) == get_next(r))
{
link(r+n, rc[r]+n);
}
else
{
link(r+n, rc[i]);
}
set_next(l, r, rc[i]);
}
inline void add(int ps, int i)
{
pos[i] = ps;
st.insert({ps, i});
connect(i);
// cout << "connect " << i << endl;
segment_add(i);
// cout << "segment_add " << i << endl;
}
inline void remv(int i)
{
int ps = pos[i];
disconnect(i);
// cout << "disconnect " << i << endl;
segment_rem(i);
// cout << "segment_rem " << i << endl;
rem(i);
// cout << "rem " << i << endl;
st.erase({ps, i});
}
void init(int N, int L, int X[])
{
n = N+1;
len = L;
Init(n*2);
// cout << "init" << endl;
for(int i = 0; i < n; i++)
{
lct[i+n]->val = 0;
upd(lct[i+n]);
}
for(int i = 0; i < n; i++)
{
link(i, i+n);
}
init_splay(n);
// cout << "init splay" << endl;
add(2e9, n-1);
for(int i = 0; i < n-1; i++)
{
add(X[i], i);
}
}
int getind(node *v)
{
if(!v) return -1;
return v->ind;
}
void prnt()
{
// for(int i = 0; i< n*2; i++)
// {
// cout << i << ": " << getind(lct[i]->p) << ' ' << getind(lct[i]->l) << ' ' << getind(lct[i]->r) << endl;
// }
// cout << endl;
}
int update(int i, int y)
{
remv(i);
add(y, i);
prnt();
int bg = st.begin()->se;
access(bg);
node *v = lct[bg];
int res = v->val + get(v->l);
// cout << "upd " << i << ' ' << y << ": " << res-1 << endl;
return res-1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9040 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9040 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9040 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9040 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9040 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
