#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
using ar = array<int,2>;
const int mxN = 150010;
const int B = 400;
int n, L, a[mxN];
unordered_map<int,int> cnt;
struct Block{
vector<int> V; ar V2[B+3];
Block(){}
void recalc(){ int j = sz(V);
for(int i = sz(V)-1; i>=0; i--){
while(j>i and V[j-1]>V[i]+L+1) j--;
if(j==sz(V)) V2[i]=ar({1,V[i]+L+1});
else V2[i]=ar({V2[j][0]+1,V2[j][1]});
}
}
Block(vector<int> XD){ V.swap(XD); recalc(); }
void add(int x){
if(++cnt[x]!=1) return;
V.insert(lb(all(V),x),x); recalc();
}
void rem(int x){
if(--cnt[x]) return;
V.erase(lb(all(V),x)); recalc();
}
};
vector<Block> bl;
bool combine(int i, int j){
if(i>j) swap(i,j);
int SZ = sz(bl[i].V)+sz(bl[j].V);
if(SZ>B) return 0; vector<int> V3(SZ);
merge(all(bl[i].V),all(bl[j].V),begin(V3));
bl[i]=Block(V3), bl.erase(begin(bl)+j); return 1;
}
void divide(int i){
int mid = sz(bl[i].V)/2; if(mid*2<B) return;
auto B1 = Block(vector<int>(begin(bl[i].V),begin(bl[i].V)+mid));
auto B2 = Block(vector<int>(begin(bl[i].V)+mid,end(bl[i].V)));
bl.insert(begin(bl)+i+1,B2); bl[i]=B1;
}
void init(int N, int l, int A[]){
bl.push_back({}); L = l; n = N;
for(int i = 0; i < n; i++)
a[i] = A[i], bl.back().add(a[i]), divide(sz(bl)-1);
}
int findBl(int x){
int l = 0, r = sz(bl)-1;
while(l<r){
int mid = (l+r)/2;
if(bl[mid].V.back()<x) l=mid+1;
else r=mid;
}
return l;
}
int update(int p, int y){
int i = findBl(a[p]);
bl[i].rem(a[p]);
int xd = i;
while(i and combine(i-1,i)) i--;
i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
a[p] = y; i = findBl(a[p]); bl[i].add(a[p]); divide(i);
int ans = 0, pos = 0;
for(Block cur : bl){
if(!sz(cur.V) or cur.V.back()<pos) continue;
auto p = lb(all(cur.V),pos)-begin(cur.V);
ans+=cur.V2[p][0], pos = cur.V2[p][1];
}
return ans;
}
Compilation message
elephants.cpp: In function 'bool combine(int, int)':
elephants.cpp:40:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
40 | if(SZ>B) return 0; vector<int> V3(SZ);
| ^~
elephants.cpp:40:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
40 | if(SZ>B) return 0; vector<int> V3(SZ);
| ^~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:73:50: warning: statement has no effect [-Wunused-value]
73 | i = xd; while(i<sz(bl)-1 and combine(i,i+1)) i;
| ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:15:8: warning: '<anonymous>.Block::V2' may be used uninitialized in this function [-Wmaybe-uninitialized]
15 | struct Block{
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
