#include "bubblesort2.h"
#include <bits/stdc++.h>
constexpr int inf = 1 << 25;
class SegTree {
int n, size;
std::vector<int> data;
public:
SegTree() {}
SegTree(const std::vector<int> &vec) {
n = (int)vec.size();
size = 1;
while (size < n) size *= 2;
data.assign(2 * size, 0);
std::copy(vec.begin(), vec.end(), data.begin() + size);
for (int i = size - 1; i >= 1; --i) data[i] = data[2 * i] + data[2 * i + 1];
}
void set(int i, int v) {
i += size;
data[i] = v;
while (i != 1) {
i /= 2;
data[i] = data[2 * i] + data[2 * i + 1];
}
}
int fold(int l, int r) {
int ret = 0;
for (l += size, r += size; l < r; l /= 2, r /= 2) {
if (l & 1) ret += data[l++];
if (r & 1) ret += data[--r];
}
return ret;
}
};
using T = std::pair<int, int>;
struct kDTree {
int xMn, xMx, yMn, yMx;
int val, lazy;
kDTree *l = nullptr, *r = nullptr;
kDTree(std::vector<T> &vec, bool divx) {
val = lazy = 0;
xMn = yMn = inf, xMx = yMx = -inf;
const int n = (int)vec.size();
for (int i = 0; i < n; ++i) {
const auto &[x, y] = vec[i];
xMn = std::min(xMn, x);
xMx = std::max(xMx, x);
yMn = std::min(yMn, y);
yMx = std::max(yMx, y);
}
if (n == 1) return;
const int m = n / 2;
if (divx) {
std::nth_element(vec.begin(), vec.begin() + m, vec.end(), [&](const auto &a, const auto &b) {
return a.first < b.first;
});
} else {
std::nth_element(vec.begin(), vec.begin() + m, vec.end(), [&](const auto &a, const auto &b) {
return a.second < b.second;
});
}
std::vector<T> lVec, rVec;
std::copy(vec.begin(), vec.begin() + m, std::back_inserter(lVec));
std::copy(vec.begin() + m, vec.end(), std::back_inserter(rVec));
l = new kDTree(lVec, not divx);
r = new kDTree(rVec, not divx);
}
void all_apply(int f) {
val += f;
lazy += f;
}
void push() {
if (l != nullptr) l->all_apply(lazy);
if (r != nullptr) r->all_apply(lazy);
lazy = 0;
}
void add(int x1, int x2, int y1, int y2, int v) {
push();
if (x2 < xMn or x1 > xMx or y2 < yMn or y1 > yMx) return;
if (x1 <= xMn and xMx <= x2 and y1 <= yMn and yMx <= y2) {
all_apply(v);
return;
}
l->add(x1, x2, y1, y2, v);
r->add(x1, x2, y1, y2, v);
if (l != nullptr) val = std::max(val, l->val);
if (r != nullptr) val = std::max(val, r->val);
}
int calc(int x1, int x2, int y1, int y2) {
push();
if (x2 < xMn or x1 > xMx or y2 < yMn or y1 > yMx) return 0;
if (x1 <= xMn and xMx <= x2 and y1 <= yMn and yMx <= y2) {
return val;
}
return std::max(l->calc(x1, x2, y1, y2), r->calc(x1, x2, y1, y2));
}
};
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
const int N = (int)A.size(), Q = (int)X.size();
{
std::vector<int> vals;
std::copy(A.begin(), A.end(), std::back_inserter(vals));
std::copy(V.begin(), V.end(), std::back_inserter(vals));
std::sort(vals.begin(), vals.end());
vals.erase(std::unique(vals.begin(), vals.end()), vals.end());
for (auto &e : A) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
for (auto &e : V) e = (int)(std::lower_bound(vals.begin(), vals.end(), e) - vals.begin());
}
std::vector<T> vec;
for (int i = 0; i < N; ++i) {
vec.push_back({i, A[i]});
}
for (int i = 0; i < Q; ++i) {
vec.push_back({X[i], V[i]});
}
std::sort(vec.begin(), vec.end());
vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
kDTree tree(vec, true);
for (const auto &[x, y] : vec) tree.add(x, x, y, y, -inf);
for (int i = 0; i < N; ++i) {
tree.add(i, i, A[i], A[i], inf);
tree.add(i + 1, N - 1, 0, A[i] - 1, 1);
}
std::vector<int> answer(Q);
for (int q = 0; q < Q; ++q) {
const int x = X[q], newVal = V[q];
const int preVal = A[x];
tree.add(x + 1, N - 1, 0, preVal - 1, -1);
tree.add(x + 1, N - 1, 0, newVal - 1, 1);
tree.add(x, x, preVal, preVal, -inf);
tree.add(x, x, newVal, newVal, inf);
answer[q] = tree.calc(0, N - 1, 0, inf);
A[x] = newVal;
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
241 ms |
3968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
