#include "elephants.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=150050;
int koren=400;
int n,a[N],L,res,nq;
int dp[1500][1500],poslednji[1500][1500];
vector<int>A[N];
void Calcblok(int i){
if(A[i].empty()) return;
for(int j=A[i].size()-1,k=A[i].size()-1;j>=0;j--){
while(A[i][j]+L<A[i][k-1]) k--;
if(A[i][j]+L>=A[i].back()){
dp[i][j]=1;
poslednji[i][j]=j;
}
else{
dp[i][j]=1+dp[i][k];
poslednji[i][j]=poslednji[i][k];
}
}
}
void Erase(int x){
for(int i=0;i<koren;i++){
if(A[i].empty()) break;
if(A[i][0]<=x && x<=A[i].back()){
int ind=A[i].size();
for(int j=0;j<=A[i].size();j++){
if(A[i][j]==x) ind=j;
}
while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
A[i].pop_back();
break;
}
}
}
void Insert(int x){
for(int i=0;i<koren;i++){
if(A[i].empty()) break;
if(x<A[i][0] || A[i+1].empty()){
if(i!=0 && !A[i+1].empty()) i--;
A[i].pb(x);
int ind=A[i].size()-1;
while(ind>=1 && A[i][ind]<A[i][ind-1]){swap(A[i][ind],A[i][ind-1]);ind--;}
Calcblok(i);
break;
}
}
}
void Calc(){
int b[n+10];for(int i=0;i<n;i++) b[i]=a[i];
sort(b,b+n);
for(int i=0;i<=koren+50;i++) A[i].clear();
for(int i=0;i<n;i++) A[i/koren].pb(b[i]);
for(int i=0;i<koren+50;i++) Calcblok(i);
}
void init(int N1, int L1, int X[]){
n = N1;
for(int i=0;i<n;i++) a[i]=X[i];
L=L1;
Calc();
for(int i=0;i<50;i++){
if(A[i].empty())break;
/*for(auto j:A[i]) printf("%i ",j);printf("\n");
for(int j=0;j<A[i].size();j++) printf("%i ",dp[i][j]);printf("\n");
for(int j=0;j<A[i].size();j++) printf("%i ",poslednji[i][j]);printf("\n");*/
}
}
int update(int qind, int y){
Erase(a[qind]);
a[qind]=y;
Insert(a[qind]);
nq++;
if(nq>=koren) {Calc();nq-=koren;}
/*printf("\n");
for(int i=0;i<koren+50;i++){
if(A[i].empty())break;
for(auto j:A[i]) printf("%i ",j);printf("\n");
}
printf("\n");*/
int res=0;
int x=A[0][0];
//printf("da");
for(int i=0;i<koren+50;i++){
//printf("%i ",x);
if(A[i].empty()) break;
if(x<=A[i].back()){
int ind=0;
for(int j=A[i].size()-1;j>=0;j--) if(A[i][j]>=x) ind=j;
res+=dp[i][ind];
x=A[i][poslednji[i][ind]]+L+1;
}
}
//printf("\n");
return res;
}
Compilation message
elephants.cpp: In function 'void Erase(int)':
elephants.cpp:33:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j=0;j<=A[i].size();j++){
| ~^~~~~~~~~~~~~
elephants.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | while(ind+1<A[i].size()){swap(A[i][ind],A[i][ind+1]);ind++;}
| ~~~~~^~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
