#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define MN 500071
int n, q, ma_val;
struct nod {
int mi, ma, nr_activ;
int lazy;
} V[4 * MN];
void prop(int u, int s, int d) {
V[u].mi += V[u].lazy;
V[u].ma += V[u].lazy;
if(s != d) {
V[u << 1].lazy += V[u].lazy;
V[u << 1 | 1].lazy += V[u].lazy;
}
V[u].lazy = 0;
}
void update_range(int l, int r, int v, int u = 1, int s = 1, int d = ma_val) {
if(r < s || d < l) return;
prop(u, s, d);
if(l <= s && d <= r) {
V[u].lazy = v;
prop(u, s, d);
return;
}
update_range(l, r, v, u << 1, s, (s + d) >> 1);
update_range(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
}
void init(int u = 1, int s = 1, int d = ma_val) {
if(s != d) {
init(u << 1, s, (s + d) >> 1);
init(u << 1 | 1, ((s + d) >> 1) + 1, d);
}
V[u].ma = V[u].nr_activ = V[u].lazy = 0;
V[u].mi = INT_MAX;
}
void update_active(int p, int v, int u = 1, int s = 1, int d = ma_val) {
prop(u, s, d);
if(d < p || p < s) return;
if(s == d) {
V[u].nr_activ = v;
if(!V[u].nr_activ) V[u].ma = V[u].lazy = 0, V[u].mi = INT_MAX;
return;
}
update_active(p, v, u << 1, s, (s + d) >> 1);
update_active(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u].nr_activ = V[u << 1].nr_activ + V[u << 1 | 1].nr_activ;
V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
if(!V[u].nr_activ) V[u].ma = V[u].lazy = 0, V[u].mi = INT_MAX;
}
int query_smaller(int p, int u = 1, int s = 1, int d = ma_val) {
prop(u, s, d);
if(p <= s) return 0;
if(d < p) return V[u].nr_activ;
return query_smaller(p, u << 1, s, (s + d) >> 1) + query_smaller(p, u << 1 | 1, ((s + d) >> 1) + 1, d);
}
void update_val(int p, int v, int u = 1, int s = 1, int d = ma_val) {
prop(u, s, d);
if(p < s || d < p) return;
if(s == d) {
V[u].ma = V[u].mi = v;
return;
}
update_val(p, v, u << 1, s, (s + d) >> 1);
update_val(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u].mi = min(V[u << 1].mi, V[u << 1 | 1].mi);
V[u].ma = max(V[u << 1].ma, V[u << 1 | 1].ma);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> VQ){
n = A.size(), q = X.size();
vector<pair<int, int> > Ord;
map<pair<int, int>, int> MNorm;
for(int i = 0; i < n; ++i) Ord.push_back({A[i], i});
for(int i = 0; i < q; ++i)
Ord.push_back({VQ[i], X[i]});
sort(Ord.begin(), Ord.end());
for(int i = 0; i < Ord.size(); ++i) MNorm[Ord[i]] = i + 1;
for(int i = 0; i < n; ++i) A[i] = MNorm[{A[i], i}];
for(int i = 0; i < q; ++i) VQ[i] = MNorm[{VQ[i], X[i]}];
ma_val = Ord.size();
init();
for(int i = 0; i < n; ++i)
update_active(A[i], 1);
for(int i = 0; i < n; ++i)
update_val(A[i], i - query_smaller(A[i]));
vector<int> answer;
for(int i = 0; i < q; ++i) {
int poz = X[i], val = VQ[i];
update_active(A[poz], 0);
update_range(A[poz] + 1, ma_val, 1);
A[poz] = val;
update_active(A[poz], 1);
update_val(A[poz], poz - query_smaller(A[poz]));
update_range(A[poz] + 1, ma_val, -1);
answer.push_back(max(abs(V[1].ma), abs(V[1].mi)));
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < Ord.size(); ++i) MNorm[Ord[i]] = i + 1;
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
3656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
