#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10, inf=1e9, S=450, S2=400;
int n, m, len, a[N];
pair<int, int> pos[N];
vector<pair<int, int>> vv;
int cnt_query;
struct Block{
vector<int> v, nxt, jump, cnt;
int lazy, id;
Block(){ lazy=-1; id=0; }
void push(){
if (lazy!=-1){
for (int i=0; i<(int)v.size(); ++i){
nxt[i]=lazy;
jump[i]=lazy;
cnt[i]=1;
}
lazy=-1;
}
}
void calc(){
for (int i=0; i<(int)v.size(); ++i) pos[v[i]]={id, i};
for (int i=(int)v.size()-1; i>=0; --i){
if (pos[nxt[i]].first!=id){
jump[i]=nxt[i];
cnt[i]=1;
}else{
jump[i]=jump[pos[nxt[i]].second];
cnt[i]=cnt[pos[nxt[i]].second]+1;
}
}
}
int get_nxt(int i){
if (lazy==-1) return nxt[i];
return lazy;
}
} bl[N/S+10];
void build(bool p){
vector<pair<int, int>> v;
if (!p){
v.emplace_back(n, n);
for (int i=n-1, j=n; i>=0; --i){
while (vv[j-1].first-vv[i].first>len) --j;
v.emplace_back(i, j);
}
reverse(v.begin(), v.end());
}else{
for (int i=0; i<=m; ++i){
bl[i].push();
for (int j=0; j<(int)bl[i].v.size(); ++j) v.emplace_back(bl[i].v[j], bl[i].nxt[j]);
bl[i].v.clear();
bl[i].nxt.clear();
bl[i].jump.clear();
bl[i].cnt.clear();
}
}
m=0;
for (int i=0; i<=n; ++i){
if ((int)bl[m].v.size()==S || i==n) ++m;
bl[m].id=m;
pos[v[i].first]={m, bl[m].v.size()};
bl[m].v.push_back(v[i].first);
bl[m].nxt.push_back(v[i].second);
bl[m].jump.push_back(0);
bl[m].cnt.push_back(0);
}
bl[m].jump[0]=n;
for (int i=0; i<m; ++i){
bl[i].calc();
}
}
void update(int l, int r, int val){
if (pos[l].first==pos[r].first){
int id=pos[l].first;
bl[id].push();
for (int i=pos[l].second; i<=pos[r].second; ++i){
bl[id].nxt[i]=val;
}
bl[id].calc();
return;
}
{
int id=pos[l].first;
bl[id].push();
for (int i=pos[l].second; i<(int)bl[id].v.size(); ++i) bl[id].nxt[i]=val;
bl[id].calc();
}
{
int id=pos[r].first;
bl[id].push();
for (int i=0; i<=pos[r].second; ++i) bl[id].nxt[i]=val;
bl[id].calc();
}
for (int i=pos[l].first+1; i<pos[r].first; ++i) bl[i].lazy=val;
}
int get(){
pair<int, int> p={0, 0};
int ans=0;
while (p.first!=m){
if (bl[p.first].lazy==-1){
ans+=bl[p.first].cnt[p.second];
p=pos[bl[p.first].jump[p.second]];
}else{
++ans;
p=pos[bl[p.first].lazy];
}
}
return ans;
}
void init(int32_t _N, int32_t L, int32_t X[])
{
n=_N;
len=L;
for (int i=0; i<n; ++i) a[i]=X[i];
a[n]=inf;
for (int i=0; i<n; ++i){
vv.emplace_back(a[i], i);
}
sort(vv.begin(), vv.end());
build(0);
}
int32_t update(int32_t _i, int32_t _y)
{
++cnt_query;
cout << cnt_query << endl;
if (cnt_query%S2==0){
build(1);
}
int i=_i, y=_y;
int tl=-1, tr=-1, tt=-1;
{
int id=m;
while (id>=0){
if (pos[bl[id].get_nxt(0)]>pos[i]) --id;
else{
for (int j=(int)bl[id].v.size()-1; j>=0; --j){
if (pos[bl[id].get_nxt(j)]<=pos[i]){
tr=bl[id].v[j];
break;
}
}
break;
}
}
}
{
int id=0;
while (1){
if (pos[bl[id].get_nxt((int)bl[id].v.size()-1)]<pos[i]) ++id;
else{
for (int j=0; j<(int)bl[id].v.size(); ++j){
if (pos[bl[id].get_nxt(j)]>=pos[i]){
tl=bl[id].v[j];
break;
}
}
break;
}
}
}
{
pair<int, int> p=pos[i];
++p.second;
if (p.second>=(int)bl[p.first].v.size()) ++p.first, p.second=0;
tt=bl[p.first].v[p.second];
}
if (tl!=-1 && tr!=-1 && pos[tl]<=pos[tr]){
update(tl, tr, tt);
}
bl[pos[i].first].v.erase(bl[pos[i].first].v.begin()+pos[i].second);
bl[pos[i].first].nxt.erase(bl[pos[i].first].nxt.begin()+pos[i].second);
bl[pos[i].first].jump.erase(bl[pos[i].first].jump.begin()+pos[i].second);
bl[pos[i].first].cnt.erase(bl[pos[i].first].cnt.begin()+pos[i].second);
bl[pos[i].first].calc();
pair<int, int> p={-1, -1}, p2={-1, -1};
{
a[i]=y;
int id=m-1;
while (1){
if (id && make_pair(a[bl[id].v[0]], bl[id].v[0])>make_pair(a[i], i)) --id;
else{
p={id, 0};
for (int j=0; j<(int)bl[id].v.size(); ++j){
if (make_pair(a[bl[id].v[j]], bl[id].v[j])<=make_pair(a[i], i)){
p={id, j+1};
}
}
break;
}
}
}
bl[p.first].push();
bl[p.first].v.insert(bl[p.first].v.begin()+p.second, i);
{
int id=0;
while (1){
if (make_pair(a[bl[id].v.back()], bl[id].v.back())<make_pair(a[i]+len, inf)) ++id;
else{
for (int j=0; j<(int)bl[id].v.size(); ++j){
if (make_pair(a[bl[id].v[j]], bl[id].v[j])>=make_pair(a[i]+len, inf)){
p2={id, j};
break;
}
}
break;
}
}
}
bl[p.first].nxt.insert(bl[p.first].nxt.begin()+p.second, bl[p2.first].v[p2.second]);
bl[p.first].jump.insert(bl[p.first].jump.begin()+p.second, 0);
bl[p.first].cnt.insert(bl[p.first].cnt.begin()+p.second, 0);
bl[p.first].calc();
p2=p;
++p2.second;
if (p2.second==(int)bl[p2.first].v.size()) ++p2.first, p2.second=0;
{
tl=-1, tr=-1, tt=-1;
{
int id=m;
while (id>=0){
if (id && (pos[bl[id].get_nxt(0)]>p2 || a[bl[id].v[0]]+len>=y)) --id;
else{
for (int j=(int)bl[id].v.size()-1; j>=0; --j){
if (pos[bl[id].get_nxt(j)]<=p2 && a[bl[id].v[j]]+len<y){
tr=bl[id].v[j];
break;
}
}
break;
}
}
}
{
int id=0;
while (1){
if (pos[bl[id].get_nxt((int)bl[id].v.size()-1)]<p2) ++id;
else{
for (int j=0; j<(int)bl[id].v.size(); ++j){
if (pos[bl[id].get_nxt(j)]>=p2){
tl=bl[id].v[j];
break;
}
}
break;
}
}
}
if (tl!=-1 && tr!=-1 && pos[tl]<=pos[tr]){
update(tl, tr, i);
}
}
return get();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
