#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
template <typename T>
struct segment_tree {
vector<T> tree;
vector<T> lazy;
T neutral;
function<T(T, T)> join;
int size;
segment_tree() {}
segment_tree(int _size, T _neutral, function<T(T, T)> f) {
join = f;
size = _size;
tree = vector<T>(4 * size);
lazy = vector<T>(4 * size);
neutral = _neutral;
}
void prop(int l, int r, int p) {
if(lazy[p] == 0) return;
if(l < r) {
lazy[p << 1] += lazy[p];
lazy[p << 1 | 1] += lazy[p];
}
tree[p] += lazy[p];
lazy[p] = 0;
}
void point_update(int id, T val) {
point_update(1, size, id, val, 1);
}
void point_update(int l, int r, int x, T val, int p) {
prop(l, r, p);
if(l > x || r < x) {
return;
}
if(l == r) {
tree[p] = val;
return;
}
int middle = l + r >> 1;
point_update(l, middle, x, val, p << 1);
point_update(middle+1, r, x, val, p << 1 | 1);
tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
}
void range_add(int L, int R, T val) {
if(L > R) {
return;
}
range_add(1, size, L, R, val, 1);
}
void range_add(int l, int r, int L, int R, T val, int p) {
prop(l, r, p);
if(L > r || l > R) return;
if(L <= l && R >= r) {
lazy[p] += val;
prop(l, r, p);
return;
}
int middle = l + r >> 1;
range_add(l, middle, L, R, val, p << 1);
range_add(middle+1, r, L, R, val, p << 1 | 1);
tree[p] = join(tree[p << 1], tree[p << 1 |1]);
}
T get(int id) {
return query(id, id);
}
T query(int L, int R) {
if(L > R) {
return neutral;
}
return query(1, size, L, R, 1);
}
T query(int l, int r, int L, int R, int p) {
prop(l, r, p);
if(L > r || l > R) return neutral;
if(L <= l && R >= r) return tree[p];
int middle = l + r >> 1;
T lft = query(l, middle, L, R, p << 1);
T rgh = query(middle+1, r, L, R, p << 1 | 1);
return join(lft, rgh);
}
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int Q = (int)X.size(), N = (int)A.size();
vector<int> answer(Q);
vector<array<int, 4>> coords;
for(int i = 0; i < N; ++i) {
coords.push_back({A[i], i, i, 0});
}
for(int i = 0; i < Q; ++i) {
coords.push_back({V[i], X[i], i, 1});
}
sort(coords.begin(), coords.end());
for(int i = 0; i < (int)coords.size(); ++i) {
if(coords[i][3] == 0) {
A[coords[i][2]] = i+1;
} else {
V[coords[i][2]] = i+1;
}
}
segment_tree<int> t(N + Q, -1e9, [](int x, int y) -> int {
return x > y ? x : y;
});
segment_tree<int> bruh(N + Q, 0, [](int x, int y) -> int {
return x+y;
});
vector<int> id(N + Q);
for(int i = 0; i < N; ++i) {
id[A[i]] = i;
}
vector<int> save_A = A;
sort(A.begin(), A.end());
for(int i = 0; i < N; ++i) {
t.point_update(A[i], id[A[i]] - i);
}
A = save_A;
for(int i = 0; i < Q; ++i) {
int prv = A[X[i]];
int nxt = V[i];
A[X[i]] = V[i];
id[nxt] = id[prv];
bruh.point_update(prv, 0);
bruh.point_update(nxt, 1);
if(nxt > prv) {
t.range_add(prv, nxt, 1);
t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
} else {
t.range_add(nxt, prv, -1);
t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
}
t.point_update(prv, -1e9);
answer[i] = t.query(1, N + Q);
}
return answer;
}
Compilation message
bubblesort2.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
bubblesort2.cpp:31:3: required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
bubblesort2.cpp:122:36: required from here
bubblesort2.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int middle = l + r >> 1;
| ~~^~~
bubblesort2.cpp: In instantiation of 'void segment_tree<T>::range_add(int, int, int, int, T, int) [with T = int]':
bubblesort2.cpp:53:3: required from 'void segment_tree<T>::range_add(int, int, T) [with T = int]'
bubblesort2.cpp:133:27: required from here
bubblesort2.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
64 | int middle = l + r >> 1;
| ~~^~~
bubblesort2.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
bubblesort2.cpp:78:32: required from 'T segment_tree<T>::query(int, int) [with T = int]'
bubblesort2.cpp:134:53: required from here
bubblesort2.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int middle = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
3076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
