#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef vector<vector<int>> vii;
typedef pair<int,int> pii;
int n,l;
int x[1500001];
int blk = 500;
struct bucket{
int sz;
int x[1001];
int cnt[1001];
int reach[1001];
void calc(){
int t = sz;
for(int i=sz-1;i>=0;i--){
while(t && x[t-1] > x[i]+l)t--;
if(t == sz){
cnt[i] = 1;
reach[i] = x[i]+l;
}else{
cnt[i] = cnt[t]+1;
reach[i] = reach[t];
}
}
}
void add(int y){
int p = ub(x,x+sz,y) - x;
sz++;
for(int i=sz-1;i>p;i--)x[i] = x[i-1];
x[p] = y;
calc();
}
void del(int y){
int p = lb(x,x+sz,y) - x;
sz--;
for(int i=p;i<sz;i++)x[i] = x[i+1];
calc();
}
}b[500];
int bcnt = 0;
void init(int N, int L, int X[])
{
n = N;
l = L;
for(int i=0;i<n;i++)x[i] = X[i];
for(int i=0;i<n;i+=blk){
for(int j=i;j<min(i+blk,n);j++){
b[bcnt].x[b[bcnt].sz++] = x[j];
}
b[bcnt++].calc();
}
//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
//cout<<"BUILT"<<'\n';
}
void rebuild(){
vector<int>nx;
for(int i=0;i<bcnt;i++){
for(int j=0;j<b[i].sz;j++){
nx.pb(b[i].x[j]);
}
}
bcnt = 0;
for(int i=0;i<n;i+=blk){
b[bcnt].sz = 0;
for(int j=i;j<min(i+blk,n);j++){
b[bcnt].x[b[bcnt].sz++] = nx[j];
}
b[bcnt++].calc();
}
}
int num = 0;
int update(int i, int y)
{
if(num == 400){rebuild();num=0;}
int pv = x[i];
//cout<<"del"<<'\n';
for(int i=0;i<bcnt;i++){
if(b[i].x[0] <= pv && b[i].x[b[i].sz-1] >= pv){
b[i].del(y);
break;
}
}
//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
x[i] = y;
for(int i=0;i<bcnt;i++){
if((i == 0 || b[i].x[0] <= y) && (i == bcnt-1 || (b[i+1].x[0] > y))){
b[i].add(y);
break;
}
}
//cout<<"add"<<'\n';
//for(int i=0;i<n;i++)cout<<b[0].x[i]<<" "<<b[0].cnt[i]<<" "<<b[0].reach[i]<<'\n';
int ans = 0;
int cur = -1;
for(int i=0;i<bcnt;i++){
if(cur>=b[i].x[b[i].sz-1])continue;
if(cur < b[i].x[0]){
ans+=b[i].cnt[0];
cur = b[i].reach[0];
continue;
}
int p = ub(b[i].x,b[i].x+b[i].sz,cur) - b[i].x;
ans+=b[i].cnt[p];
cur=b[i].reach[p];
}
num++;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
