#include "bubblesort2.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int N = 1e6;
int ind[N];
int st[4*N+10], lz[4*N+10] = {0};
int cons(int i, int l, int r){
if(l==r) return st[i] = ind[l];
int m = l+r>>1;
return st[i] = max(cons(i<<1, l, m),cons(i<<1|1, m+1, r));
}
void upd(int i, int l, int r, int a, int v){
if(lz[i]){
st[i]+=lz[i];
if(l!=r){
lz[i<<1]+=lz[i];
lz[i<<1|1] += lz[i];
}
lz[i]=0;
}
if(r<a)return;
if(a<=l){
st[i]+=v;
if(l!=r){
lz[i<<1]+=v;
lz[i<<1|1]+=v;
}
return;
}
int m = l+r>>1;
upd(i<<1, l, m, a, v);
upd(i<<1|1, m+1, r, a, v);
st[i]=max(st[i<<1],st[i<<1|1]);
}
void updind(int i, int l, int r, int iind, int newind){
if(lz[i]){
st[i]+=lz[i];
if(l!=r){
lz[i<<1]+=lz[i];
lz[i<<1|1] += lz[i];
}
lz[i]=0;
}
if(l==r){
st[i] += newind-ind[l];
ind[l] = newind;
return;
}
int m = l+r>>1;
if(iind <= m) updind(i<<1, l, m, iind, newind);
else updind(i<<1|1, m+1, r, iind, newind);
st[i] = max(st[i<<1], st[i<<1|1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int n=A.size(), q = X.size();
long long a[n], v[q], tot[n+q];for(int i = 0;i < n;i++) tot[i] = a[i] = (long long)A[i]*n+i;
for(int i = 0;i < q;i++) tot[i+n] = v[i] = (long long)V[i]*n+X[i];
sort(tot, tot+n+q);
fill(ind,ind+N,-1);
for(int i = 0;i < n;i++) {
a[i] = lower_bound(tot, tot+n+q, a[i])-tot;
ind[a[i]]=i;
}
for(int i = 0;i < q;i++) v[i] = lower_bound(tot, tot+n+q, v[i])-tot;
cons(1, 0, N-1);
for(int i = 0;i < n;i++){
upd(1, 0, N-1, a[i]+1, -1);
}
vector<int> ans(q);
for(int _ = 0;_ < q;_++){
int i = X[_];
updind(1, 0, N-1, a[i], -1);
updind(1, 0, N-1, v[_], i);
upd(1, 0, N-1, a[i]+1, 1);
upd(1, 0, N-1, v[_]+1, -1);
a[i]=v[_];
ans[_]=st[1];
}
return ans;
}
Compilation message
bubblesort2.cpp: In function 'int cons(int, int, int)':
bubblesort2.cpp:11:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
11 | int m = l+r>>1;
| ~^~
bubblesort2.cpp: In function 'void upd(int, int, int, int, int)':
bubblesort2.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int m = l+r>>1;
| ~^~
bubblesort2.cpp: In function 'void updind(int, int, int, int, int)':
bubblesort2.cpp:51:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int m = l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
17756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
14940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
