#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using vi = vector<int>;
#define mp make_pair
#define lb lower_bound
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
const int mxN = (int)1e6+5;
vi a;
vector<pair<int,int>> v;
int seg[mxN*2], lzy[mxN*2];
void prop(int p, int l, int r){
if(l==r or !lzy[p]) return;
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
lzy[p+1]+=lzy[p], lzy[rp]+=lzy[p];
seg[p+1]+=lzy[p], seg[rp]+=lzy[p], lzy[p]=0;
}
void upd(int i, int j, int vv, int p=0, int l=1, int r=sz(v)){
if(i>r or j<l or i>j) return; prop(p,l,r);
if(i<=l and r<=j){ seg[p]+=vv,lzy[p]+=vv; return; }
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
if(i<=mid) upd(i,j,vv,p+1,l,mid);
if(j>mid) upd(i,j,vv,rp,mid+1,r);
seg[p] = max(seg[p+1],seg[rp]);
}
void add(int i, int x){
int j = lb(all(v),mp(a[i],i))-begin(v);
int j2 = lb(all(v),mp(a[i],-1))-begin(v);
upd(j,j,i*x), upd(j2,sz(v),-x);
}
vi countScans(vi A, vi x, vi y){
int n = sz(A), q = sz(x); vi ans; a.resize(n+1);
for(int i = 1; i <= n; i++) a[i]=A[i],v.pb({a[i],i});
for(int i = 0; i < q; i++) v.pb({y[i],++x[i]});
sort(all(v)); v.erase(unique(all(v)),end(v));
for(int i = 1; i <= n; i++) add(i,1);
for(int i = 0; i < q; i++)
add(x[i],-1),a[x[i]]=y[i],add(x[i],1),ans.pb(seg[0]);
return ans;
}
Compilation message
bubblesort2.cpp: In function 'void upd(int, int, int, int, int, int)':
bubblesort2.cpp:22:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
22 | if(i>r or j<l or i>j) return; prop(p,l,r);
| ^~
bubblesort2.cpp:22:35: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
22 | if(i>r or j<l or i>j) return; prop(p,l,r);
| ^~~~
bubblesort2.cpp: In function 'vi countScans(vi, vi, vi)':
bubblesort2.cpp:42:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
42 | for(int i = 0; i < q; i++)
| ^~~
bubblesort2.cpp:44:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
44 | return ans;
| ^~~~~~
| # |
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 |
23 ms |
1512 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 |
- |
