#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ll long long
#define itr ::iterator
typedef pair<int,int> pii;
const int MAX=1e5;
const int len=400;
int N,K,qcnt,pos[MAX],lol[MAX];
struct data
{
int size;
int arr[1000],dp[1000],right[1000];
data()
{
size=0;
}
void cal()
{
int ptr=size;
for(int A=size-1;A>=0;A--)
{
while(arr[ptr-1]-arr[A]>K)
--ptr;
if(ptr==size)
{
dp[A]=1;
right[A]=arr[A]+K;
}
else
{
dp[A]=1+dp[ptr];
right[A]=right[ptr];
}
}
return ;
}
void insert(int val)
{
int B=0;
for(int A=size-1;A>=0;A--)
{
if(arr[A]<=val)
{
B=A+1;
break;
}
}
for(int C=size;C>B;C--)
arr[C]=arr[C-1];
arr[B]=val;
++size;
return ;
}
void remove(int val)
{
for(int A=0;A<size;A++)
{
if(arr[A]==val)
{
for(int B=A;B<size-1;B++)
arr[B]=arr[B+1];
break;
}
}
--size;
return ;
}
} block[400];
void init(int n,int l,int X[])
{
N=n;
K=l;
for(int A=0;A<N;A++)
{
pos[A]=X[A];
block[A/len].arr[block[A/len].size]=X[A];
block[A/len].size++;
}
for(int A=0;block[A].size>0;A++)
block[A].cal();
return ;
}
int update(int idx,int val)
{
++qcnt;
int B;
for(B=0;block[B].size>0;B++)
{
if(block[B].arr[0]>pos[idx])
break;
}
if(B)
B--;
block[B].remove(pos[idx]);
block[B].cal();
pos[idx]=val;
for(B=0;block[B].size>0;B++)
{
if(block[B].arr[0]>pos[idx])
break;
}
if(B)
B--;
block[B].insert(pos[idx]);
block[B].cal();
int covered=-1,res=0;
for(int A=0;block[A].size>0;A++)
{
int cur=upper_bound(block[A].arr,block[A].arr+block[A].size,covered)-block[A].arr;
if(cur==block[A].size)
continue;
res+=block[A].dp[cur];
covered=block[A].right[cur];
}
/*for(int A=0;block[A].size>0;A++)
for(int B=0;B<block[A].size;B++)
cout<<block[A].arr[B]<<" ";
cout<<"\n";*/
if(qcnt==len-2)
{
int cur=0;
for(int A=0;block[A].size>0;A++)
{
for(int B=0;B<block[A].size;B++)
lol[cur++]=block[A].arr[B];
block[A].size=0;
}
for(int A=0;A<cur;A++)
{
pos[A]=lol[A];
block[A/len].arr[block[A/len].size]=lol[A];
block[A/len].size++;
}
for(int A=0;block[A].size>0;A++)
block[A].cal();
qcnt=0;
}
return res;
}
/*signed main()
{
ios_base::sync_with_stdio(false);
int N=4,L=10;
int X[]={10,15,17,20};
init(N,L,X);
cout<<update(2,15)<<"\n";
cout<<update(1,25)<<"\n";
cout<<update(3,35)<<"\n";
cout<<update(0,38)<<"\n";
cout<<update(2,00)<<"\n";
return 0;
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
2148 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
2148 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2296 KB |
Output is correct |
5 |
Correct |
4 ms |
2296 KB |
Output is correct |
6 |
Correct |
3 ms |
2296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
2148 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2296 KB |
Output is correct |
5 |
Correct |
4 ms |
2296 KB |
Output is correct |
6 |
Correct |
3 ms |
2296 KB |
Output is correct |
7 |
Correct |
261 ms |
3180 KB |
Output is correct |
8 |
Correct |
282 ms |
4392 KB |
Output is correct |
9 |
Correct |
362 ms |
6968 KB |
Output is correct |
10 |
Incorrect |
198 ms |
8324 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
2148 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2296 KB |
Output is correct |
5 |
Correct |
4 ms |
2296 KB |
Output is correct |
6 |
Correct |
3 ms |
2296 KB |
Output is correct |
7 |
Correct |
261 ms |
3180 KB |
Output is correct |
8 |
Correct |
282 ms |
4392 KB |
Output is correct |
9 |
Correct |
362 ms |
6968 KB |
Output is correct |
10 |
Incorrect |
198 ms |
8324 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2040 KB |
Output is correct |
2 |
Correct |
3 ms |
2148 KB |
Output is correct |
3 |
Correct |
3 ms |
2296 KB |
Output is correct |
4 |
Correct |
3 ms |
2296 KB |
Output is correct |
5 |
Correct |
4 ms |
2296 KB |
Output is correct |
6 |
Correct |
3 ms |
2296 KB |
Output is correct |
7 |
Correct |
261 ms |
3180 KB |
Output is correct |
8 |
Correct |
282 ms |
4392 KB |
Output is correct |
9 |
Correct |
362 ms |
6968 KB |
Output is correct |
10 |
Incorrect |
198 ms |
8324 KB |
Output isn't correct |
11 |
Halted |
0 ms |
0 KB |
- |