#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mxN = (int)5e4+10;
const int B = 240;
int n, L, a[mxN];
using ar = array<int,2>;
struct Block{
vector<int> V;
deque<ar> V2;
Block(){}
void recalc(){
V2.clear();
for(int i = sz(V)-1; i>=0; i--){
int pos = sz(V2)-(sz(V)- (int)(lb(all(V),V[i]+L+1)-begin(V)));
if(pos==sz(V2)) V2.pf({1,V[i]+L+1});
else V2.pf({V2[pos][0]+1,V2[pos][1]});
}
}
Block(vector<int> XD){ V.swap(XD); recalc(); }
bool contains(int x){
int pos = lb(all(V),x)-begin(V);
return (pos!=sz(V) and V[pos]==x);
}
void add(int x){
if(contains(x)) return;
V.insert(lb(all(V),x),x); recalc();
}
void rem(int x){ V.erase(lb(all(V),x)); recalc(); }
};
vector<Block> bl;
void combine(int i, int j){
if(i>j) swap(i,j);
if(sz(bl[i].V)+sz(bl[j].V)>B) return;
auto V = bl[i].V, V2 = bl[j].V;
int pi = 0, pj = 0;
vector<int> V3; V3.clear();
while(pi!=sz(V) and pj!=sz(V2)){
if(pi==sz(V)) V3.pb(V2[pj]),pj++;
else if(pj==sz(V) or V[pj]>V[pi]) V3.pb(V[pi]),pi++;
else V3.pb(V[pj]),pj++;
}
bl.erase(begin(bl)+j); bl.erase(begin(bl)+i); bl.insert(begin(bl)+i,Block(V3));
}
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.erase(begin(bl)+i); bl.insert(begin(bl)+i,B2); bl.insert(begin(bl)+i,B1);
}
void init(int N, int l, int A[]){
bl.pb({}); L = l; n = N;
for(int i = 0; i < n; i++){
a[i] = A[i]; bl[sz(bl)-1].add(a[i]); divide(sz(bl)-1);
}
}
int update(int p, int y){
for(int i = 0; i < sz(bl); i++){
if(bl[i].V.back()>=a[p] and bl[i].contains(a[p])){
bl[i].rem(a[p]);
if(i) combine(i-1,i);
if(i<sz(bl)-1) combine(i,i+1);
break;
}
}
a[p] = y;
for(int i = 0; i < sz(bl); i++){
if(i==sz(bl)-1 or bl[i].V.back() >= a[p]){
bl[i].add(a[p]); divide(i); break;
}
}
int ans = 0, pos = 0;
for(Block cur : bl){
for(auto u : cur.V) cout << u << " "; cout << "\n";
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 'int update(int, int)':
elephants.cpp:83:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
83 | for(auto u : cur.V) cout << u << " "; cout << "\n";
| ^~~
elephants.cpp:83:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
83 | for(auto u : cur.V) cout << u << " "; cout << "\n";
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
