#include <bits/stdc++.h>
using namespace std;
const int BASE = 1 << 10;
int TREE[BASE << 1];
int LAZY[BASE << 1];
int actsetindex[BASE];
map<int, int> mapa;
priority_queue<int> Q[BASE];
void push(int v, int l, int r){
TREE[l] += LAZY[v];
TREE[r] += LAZY[v];
LAZY[l] += LAZY[v];
LAZY[r] += LAZY[v];
LAZY[v] = 0;
}
void update(int v, int l, int r, int a, int b, int val){
if(r < a || b < l) return;
else if(a <= l && r <= b){
TREE[v] += val;
LAZY[v] += val;
}
else{
int mid = (l+r)/2;
push(v, 2*v, 2*v+1);
update(2*v, l, mid, a, b, val);
update(2*v+1, mid+1, r, a, b, val);
TREE[v] = max(TREE[2*v], TREE[2*v+1]);
}
}
void scale(){
int x = 0;
for(auto it = mapa.begin(); it != mapa.end(); ++it)
it->second = x++;
}
void repair(int val){
if(actsetindex[Q[val].top()] == val) return;
update(1, 0, BASE-1, val, val, -Q[val].top());
while(Q[val].size() && actsetindex[Q[val].top()] != val)
Q[val].pop();
if(Q[val].size())
update(1, 0, BASE-1, val, val, Q[val].top());
}
vector<int> countScans(vector <int> A, vector<int> X, vector<int> V){
for(auto u : A)
mapa[u];
for(auto u : V)
mapa[u];
scale();
for(int i = 0; i < A.size(); i++)
A[i] = mapa[A[i]];
for(int i = 0; i < V.size(); i++){
V[i] = mapa[V[i]];
X[i]++;
}
for(int i = 0; i < A.size(); i++){
if(Q[A[i]].size())
update(1, 0, BASE-1, A[i], A[i], -Q[A[i]].top());
update(1, 0, BASE-1, A[i], A[i], i+1);
update(1, 0, BASE-1, A[i], BASE-1, -1);
actsetindex[i+1] = A[i];
Q[A[i]].push(i+1);
}
//cout << max(TREE[1], 0) << endl;
vector<int> res;
for(int i = 0; i < V.size(); i++){
int idx = X[i];
int what = actsetindex[idx];
update(1, 0, BASE-1, what, BASE-1, 1);
repair(what);
if(Q[V[i]].size())
update(1, 0, BASE-1, V[i], V[i], -Q[V[i]].top());
Q[V[i]].push(idx);
update(1, 0, BASE-1, V[i], V[i], Q[V[i]].top());
update(1, 0, BASE-1, V[i], BASE-1, -1);
actsetindex[idx] = V[i];
res.push_bac(max(TREE[1], 0));
}
return res;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 0; i < A.size(); i++)
| ~~^~~~~~~~~~
bubblesort2.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
bubblesort2.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < A.size(); i++){
| ~~^~~~~~~~~~
bubblesort2.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < V.size(); i++){
| ~~^~~~~~~~~~
bubblesort2.cpp:109:7: error: 'class std::vector<int>' has no member named 'push_bac'; did you mean 'push_back'?
109 | res.push_bac(max(TREE[1], 0));
| ^~~~~~~~
| push_back
