#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
// constexpr int maxn = 1<<20, B = 700, inf = 0x3f3f3f3f; // subtasks brutao, mudar
#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
struct SegmentTree {
int a[maxn];
void build(int node, int i, int j) {
}
void upd(int node, int i, int j, int l, int r, int v) {
for(int i = l; i <= r; i++)
a[i] += v;
}
int query() {
int ans = 0;
for(int i = 0; i < 8010; i++)
ans = max(ans, a[i]);
return ans;
}
} seg;
void compress(vector<int>& A, vector<int>& V) {
map<int,int> mp;
for(int x : A)
mp[x] = 0;
for(int x : V)
mp[x] = 0;
int coord = 0;
for(auto& it : mp)
it.second = ++coord;
for(int& x : A)
x = mp[x];
for(int& x : V)
x = mp[x];
}
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x > 0; x -= x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(; x < maxn; x += x&-x)
ans += bit[x];
return ans;
}
void clear() { memset(bit, 0, sizeof bit); }
} bit;
vector<int> pareto;
int ans[maxn]; bool foi[maxn];
vector<pair<int,int>> qr[maxn];
int FORA[maxn], DENTRO[maxn];
void rebuild(const vector<int>& A) {
pareto.clear();
int N = (int)(A.size());
for(int i = 0; i < N; i++) {
if(foi[i]) continue;
while(pareto.size() && A[i] <= A[pareto.back()])
pareto.pop_back();
pareto.push_back(i);
}
bit.clear();
for(int i = 0; i < (int)A.size(); i++) {
while(qr[i].size()) {
auto [val, id] = qr[i].back();
qr[i].pop_back();
ans[id] = bit.query(val+1);
}
DENTRO[i] = bit.query(A[i]+1);
if(!foi[i]) seg.a[i] = DENTRO[i];
else seg.a[i] = -inf;
if(!foi[i])
bit.upd(A[i], 1);
}
seg.build(1, 0, N-1);
}
int bs(int x, const vector<int>& A) {
int l = 0, r = (int)(pareto.size())-1, ans = -1;
while(l <= r) {
int m = (l+r) >> 1;
if(A[pareto[m]] < x)
ans = pareto[m], l = m+1;
else
r = m-1;
}
return ans;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q = (int)X.size(), N = (int)A.size();
compress(A, V);
std::vector<int> answer(Q);
for(int q = 0; q < Q; q += B) {
vector<int> special;
for(int add = 0; add < B && add+q < Q; add++) {
qr[X[q+add]].push_back({V[q+add], q+add});
if(foi[X[q+add]]) continue;
foi[X[q+add]] = 1;
special.push_back(X[q+add]);
}
/* for(int i = 0; i < N; i++)
if(!foi[i]) foi[i] = 1, special.push_back(i); */
rebuild(A);
for(int add = 0; add < B && add+q < Q; add++) {
int pos = X[q+add], val = V[q+add];
/* int last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, -1); */
A[pos] = val;
{
int last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, 1);
}
int especiais = 0;
for(int x : special) {
int aq = 0;
for(int j = 0; j < x; j++)
aq += A[j] > A[x];
especiais = max(especiais, aq);
}
answer[q+add] = max(seg.query(), especiais);
}
for(int x : special)
foi[x] = 0;
}
return answer;
}
struct SegmentTree {
int tree[maxn], lazy[maxn], a[maxn];
void flush(int node, int i, int j) {
/* if(!lazy[node]) return;
if(i != j) {
lazy[node<<1] += lazy[node];
lazy[node<<1|1] += lazy[node];
}
tree[node] += lazy[node];
lazy[node] = 0; */
}
void build(int node, int i, int j) {
/* lazy[node] = 0;
if(i == j) return (void)(tree[node] = a[i]);
int m = (i+j) >> 1;
build(node<<1, i, m);
build(node<<1|1, m+1, j);
tree[node] = max(tree[node<<1], tree[node<<1|1]); */
}
void upd(int node, int i, int j, int l, int r, int v) {
/* flush(node, i, j);
if(i > r || j < l) return;
if(i >= l && j <= r) {
lazy[node] += v;
flush(node, i, j);
return;
}
int m = (i+j) >> 1;
upd(node<<1, i, m, l, r, v);
upd(node<<1|1, m+1, j, l, r, v);
tree[node] = max(tree[node<<1], tree[node<<1|1]); */
for(int i = l; i <= r; i++)
a[i] += v;
}
int query() {
int ans = 0;
for(int i = 0; i < 8010; i++)
ans = max(ans, a[i]);
return ans;
}
// int query() { return tree[1] + lazy[1]; } // quero o maximo geral mesmo
} seg;
void compress(vector<int>& A, vector<int>& V) {
map<int,int> mp;
for(int x : A)
mp[x] = 0;
for(int x : V)
mp[x] = 0;
int coord = 0;
for(auto& it : mp)
it.second = ++coord;
for(int& x : A)
x = mp[x];
for(int& x : V)
x = mp[x];
}
struct BIT {
int bit[maxn];
void upd(int x, int v) {
for(; x > 0; x -= x&-x)
bit[x] += v;
}
int query(int x) {
int ans = 0;
for(; x < maxn; x += x&-x)
ans += bit[x];
return ans;
}
void clear() { memset(bit, 0, sizeof bit); }
} bit;
vector<int> pareto;
int ans[maxn]; bool foi[maxn];
vector<pair<int,int>> qr[maxn];
int FORA[maxn], DENTRO[maxn];
void rebuild(const vector<int>& A) {
pareto.clear();
int N = (int)(A.size());
for(int i = 0; i < N; i++) {
if(foi[i]) continue;
while(pareto.size() && A[i] <= A[pareto.back()])
pareto.pop_back();
pareto.push_back(i);
}
bit.clear();
for(int i = 0; i < (int)A.size(); i++) {
while(qr[i].size()) {
auto [val, id] = qr[i].back();
qr[i].pop_back();
ans[id] = bit.query(val+1);
}
DENTRO[i] = bit.query(A[i]+1);
seg.a[i] = DENTRO[i], bit.upd(A[i], 1);
}
seg.build(1, 0, N-1);
}
int bs(int x, const vector<int>& A) {
int l = 0, r = (int)(pareto.size())-1, ans = -1;
while(l <= r) {
int m = (l+r) >> 1;
if(A[pareto[m]] < x)
ans = pareto[m], l = m+1;
else
r = m-1;
}
return ans;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int Q = (int)X.size(), N = (int)A.size();
compress(A, V);
std::vector<int> answer(Q);
for(int q = 0; q < Q; q += B) {
vector<int> special;
for(int add = 0; add < B && add+q < Q; add++) {
qr[X[q+add]].push_back({V[q+add], q+add});
if(foi[X[q+add]]) continue;
foi[X[q+add]] = 1;
special.push_back(X[q+add]);
}
/* for(int i = 0; i < N; i++)
if(!foi[i]) foi[i] = 1, special.push_back(i); */
rebuild(A);
// memset(FORA, 0, sizeof FORA);
// memset(ans, 0, sizeof ans);
/* for(int x : special)
FORA[x] = 0;
for(int x : special)
for(int y : special)
if(x < y && A[x] > A[y]) ++FORA[y]; */
for(int add = 0; add < B && add+q < Q; add++) {
int pos = X[q+add], val = V[q+add];
int last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, -1);
/* for(int x : special) {
if(pos < x && A[pos] > A[x]) --FORA[x];
if(x < pos && A[x] > A[pos]) --FORA[pos];
} */
// DENTRO[pos] = ans[q+add];
A[pos] = val;
last = bs(A[pos], A);
if(last > pos)
seg.upd(1, 0, N-1, pos, last, 1);
// db
/* DENTRO[pos] = 0;
for(int j = 0; j < pos; j++)
if(!foi[j] && A[j] > val) DENTRO[pos]++; */
/* for(int x : special) {
if(pos < x && A[pos] > A[x]) ++FORA[x];
if(x < pos && A[x] > A[pos]) ++FORA[pos];
} */
int especiais = 0;
for(int x : special) {
// especiais = max(especiais, FORA[x] + DENTRO[x]);
int aq = 0;
for(int j = 0; j < x; j++)
aq += A[j] > A[x];
especiais = max(especiais, aq);
}
answer[q+add] = max(seg.query(), especiais);
}
for(int x : special)
foi[x] = 0;
}
return answer;
}
Compilation message
bubblesort2.cpp:11:15: error: redefinition of 'constexpr const int maxn'
11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^~~~
bubblesort2.cpp:5:15: note: 'constexpr const int maxn' previously defined here
5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^~~~
bubblesort2.cpp:11:29: error: redefinition of 'constexpr const int B'
11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^
bubblesort2.cpp:5:29: note: 'constexpr const int B' previously defined here
5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^
bubblesort2.cpp:11:36: error: redefinition of 'constexpr const int inf'
11 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^~~
bubblesort2.cpp:5:36: note: 'constexpr const int inf' previously defined here
5 | constexpr int maxn = 1<<20, B = 1, inf = 0x3f3f3f3f; // subtasks brutao, mudar
| ^~~
bubblesort2.cpp:161:8: error: redefinition of 'struct SegmentTree'
161 | struct SegmentTree {
| ^~~~~~~~~~~
bubblesort2.cpp:13:8: note: previous definition of 'struct SegmentTree'
13 | struct SegmentTree {
| ^~~~~~~~~~~
bubblesort2.cpp:202:3: error: conflicting declaration 'int seg'
202 | } seg;
| ^~~
bubblesort2.cpp:27:3: note: previous declaration as 'SegmentTree seg'
27 | } seg;
| ^~~
bubblesort2.cpp:204:6: error: redefinition of 'void compress(std::vector<int>&, std::vector<int>&)'
204 | void compress(vector<int>& A, vector<int>& V) {
| ^~~~~~~~
bubblesort2.cpp:29:6: note: 'void compress(std::vector<int>&, std::vector<int>&)' previously defined here
29 | void compress(vector<int>& A, vector<int>& V) {
| ^~~~~~~~
bubblesort2.cpp:221:8: error: redefinition of 'struct BIT'
221 | struct BIT {
| ^~~
bubblesort2.cpp:46:8: note: previous definition of 'struct BIT'
46 | struct BIT {
| ^~~
bubblesort2.cpp:234:3: error: conflicting declaration 'int bit'
234 | } bit;
| ^~~
bubblesort2.cpp:59:3: note: previous declaration as 'BIT bit'
59 | } bit;
| ^~~
bubblesort2.cpp:236:13: error: redefinition of 'std::vector<int> pareto'
236 | vector<int> pareto;
| ^~~~~~
bubblesort2.cpp:61:13: note: 'std::vector<int> pareto' previously declared here
61 | vector<int> pareto;
| ^~~~~~
bubblesort2.cpp:238:5: error: redefinition of 'int ans [1048576]'
238 | int ans[maxn]; bool foi[maxn];
| ^~~
bubblesort2.cpp:63:5: note: 'int ans [1048576]' previously declared here
63 | int ans[maxn]; bool foi[maxn];
| ^~~
bubblesort2.cpp:238:21: error: redefinition of 'bool foi [1048576]'
238 | int ans[maxn]; bool foi[maxn];
| ^~~
bubblesort2.cpp:63:21: note: 'bool foi [1048576]' previously declared here
63 | int ans[maxn]; bool foi[maxn];
| ^~~
bubblesort2.cpp:239:23: error: redefinition of 'std::vector<std::pair<int, int> > qr [1048576]'
239 | vector<pair<int,int>> qr[maxn];
| ^~
bubblesort2.cpp:64:23: note: 'std::vector<std::pair<int, int> > qr [1048576]' previously declared here
64 | vector<pair<int,int>> qr[maxn];
| ^~
bubblesort2.cpp:240:5: error: redefinition of 'int FORA [1048576]'
240 | int FORA[maxn], DENTRO[maxn];
| ^~~~
bubblesort2.cpp:65:5: note: 'int FORA [1048576]' previously declared here
65 | int FORA[maxn], DENTRO[maxn];
| ^~~~
bubblesort2.cpp:240:17: error: redefinition of 'int DENTRO [1048576]'
240 | int FORA[maxn], DENTRO[maxn];
| ^~~~~~
bubblesort2.cpp:65:17: note: 'int DENTRO [1048576]' previously declared here
65 | int FORA[maxn], DENTRO[maxn];
| ^~~~~~
bubblesort2.cpp:242:6: error: redefinition of 'void rebuild(const std::vector<int>&)'
242 | void rebuild(const vector<int>& A) {
| ^~~~~~~
bubblesort2.cpp:67:6: note: 'void rebuild(const std::vector<int>&)' previously defined here
67 | void rebuild(const vector<int>& A) {
| ^~~~~~~
bubblesort2.cpp:266:5: error: redefinition of 'int bs(int, const std::vector<int>&)'
266 | int bs(int x, const vector<int>& A) {
| ^~
bubblesort2.cpp:96:5: note: 'int bs(int, const std::vector<int>&)' previously defined here
96 | int bs(int x, const vector<int>& A) {
| ^~
bubblesort2.cpp:278:18: error: redefinition of 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)'
278 | std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
| ^~~~~~~~~~
bubblesort2.cpp:108:18: note: 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)' previously defined here
108 | std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
| ^~~~~~~~~~
