#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define int long long
template<class T>
using ordered_set=
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct Node{
int lazy;
Node *tl, *tr;
Node (){
lazy=-1;
tl=nullptr;
tr=nullptr;
}
void apply(int x){
lazy=x;
}
void push(){
if (lazy!=-1){
tl->apply(lazy);
tr->apply(lazy);
lazy=-1;
}
}
void operator~(){
if (tl!=nullptr){
delete tl;
delete tr;
}
delete this;
}
};
struct SegmentTree{
Node *root;
void update(Node *t, int l, int r, int L, int R, int val){
if (r<L || R<l) return;
if (L<=l && r<=R){
t->apply(val);
return;
}
if (t->tl==nullptr){
t->tl=new Node();
t->tr=new Node();
}
t->push();
int mid=(l+r)>>1;
update(t->tl, l, mid, L, R, val);
update(t->tr, mid+1, r, L, R, val);
}
int get(Node *t, int l, int r, int pos){
if (l==r) return t->lazy;
t->push();
int mid=(l+r)>>1;
if (pos<=mid) return get(t->tl, l, mid, pos);
return get(t->tr, mid+1, r, pos);
}
} seg;
const int N=2e5+10, inf=1e9;
int n, len, pos[N], nxt[N], dist[N];
ordered_set<pair<int, int>> st;
void init(int32_t _N, int32_t L, int32_t X[])
{
n = _N, len=L;
seg.root=new Node();
for (int i=0; i<n; ++i) pos[i]=X[i];
vector<pair<int, int>> v;
for (int i=0; i<n; ++i) v.emplace_back(pos[i], i);
pos[n]=inf;
v.emplace_back(inf, n);
sort(v.begin(), v.end());
for (int i=0, j=0; i<n; ++i){
while (j<n && v[j].first-v[i].first<=len) ++j;
nxt[v[i].second]=(j==n?n:v[j].second);
}
dist[n]=0;
for (int i=n-1; i>=0; --i) dist[v[i].second]=dist[nxt[v[i].second]]+1;
for (int i=0; i<=n; ++i) seg.update(seg.root, 0, 1e18, pos[i]*(n+1)+i, pos[i]*(n+1)+i, dist[i]);
for (auto &i:v) st.insert(i);
}
int32_t update(int32_t _i, int32_t _y)
{
int i=_i;
auto it=st.find({pos[i], i});
int id=st.order_of_key({pos[i], i})+1;
if (it!=st.begin()){
int pl, pr;
{
int l=0, r=n-1;
while (l<=r){
int mid=(l+r)>>1;
auto it2=st.find_by_order(mid);
int id2=st.order_of_key({it2->first+len, inf});
if (id2>id) r=mid-1;
else l=mid+1;
}
pr=r;
}
{
int l=0, r=n-1;
while (l<=r){
int mid=(l+r)>>1;
auto it2=st.find_by_order(mid);
int id2=st.order_of_key({it2->first+len, inf});
if (id2>=id) r=mid-1;
else l=mid+1;
}
pl=l;
}
int d=seg.get(seg.root, 0, 1e18, pos[prev(it)->second]*(n+1)+prev(it)->second);
if (pl<=pr){
auto itl=st.find_by_order(pl), itr=st.find_by_order(pr);
seg.update(seg.root, 0, 1e18, itl->first*(n+1)+itl->second, itr->first*(n+1)+itr->second, d+1);
}
}
st.erase(it);
pos[i]=_y;
st.insert({pos[i], i});
it=st.find({pos[i], i});
id=st.order_of_key(*it);
auto tmp=st.upper_bound({pos[i]+len, inf});
dist[i]=seg.get(seg.root, 0, 1e18, pos[tmp->second]*(n+1)+tmp->second)+1;
seg.update(seg.root, 0, 1e18, pos[i]*(n+1)+i, pos[i]*(n+1)+i, dist[i]);
if (it!=st.begin()){
int pl, pr;
{
int l=0, r=n-1;
while (l<=r){
int mid=(l+r)>>1;
auto it2=st.find_by_order(mid);
int id2=st.order_of_key({it2->first+len, inf});
if (id2>id) r=mid-1;
else l=mid+1;
}
pr=r;
}
{
int l=0, r=n-1;
while (l<=r){
int mid=(l+r)>>1;
auto it2=st.find_by_order(mid);
int id2=st.order_of_key({it2->first+len, inf});
if (id2>=id) r=mid-1;
else l=mid+1;
}
pl=l;
}
if (pl<=pr){
auto itl=st.find_by_order(pl), itr=st.find_by_order(pr);
seg.update(seg.root, 0, 1e18, itl->first*(n+1)+itl->second, itr->first*(n+1)+itr->second, dist[i]+1);
}
}
return seg.get(seg.root, 0, 1e18, st.begin()->first*(n+1)+st.begin()->second);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
