#include "bubblesort2.h"
#include <bits/stdc++.h>
constexpr int inf = 1E9;
struct Info {
int x;
Info(int x = -inf) : x(x) {}
};
Info operator+(const Info &a, const Info &b) {
return Info(std::max(a.x, b.x));
}
struct Tag {
int add;
Tag(int add = 0) : add(add) {}
};
void apply(Tag &a, const Tag &b) {
a.add += b.add;
}
void apply(Info &a, const Tag &b) {
a.x += b.add;
}
template<class Info, class Tag,
class Merge = std::plus<Info>>
struct LazySegmentTree {
const int n;
const Merge merge;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)), tag(4 << std::__lg(n)) {}
LazySegmentTree(std::vector<Info> init) : LazySegmentTree(init.size()) {
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = merge(info[2 * p], info[2 * p + 1]);
}
void apply(int p, const Tag &v) {
::apply(info[p], v);
::apply(tag[p], v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, Info v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int x, Info v) {
modify(1, 0, n, x, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
};
std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
int Q = x.size();
int n = a.size();
std::vector<int> answer(Q);
std::vector<std::pair<int, int>> f;
for (int i = 0; i < n; i++) {
f.emplace_back(a[i], i);
}
for (int i = 0; i < Q; i++) {
f.emplace_back(v[i], x[i]);
}
std::sort(f.begin(), f.end());
f.erase(std::unique(f.begin(), f.end()), f.end());
int m = f.size();
LazySegmentTree<Info, Tag> s(m);
auto add = [&](int x, int v) {
int p = std::lower_bound(f.begin(), f.end(), std::pair(v, x)) - f.begin();
s.rangeApply(p, p + 1, Tag(inf + x));
s.rangeApply(p, m, Tag(-1));
};
auto rem = [&](int x, int v) {
int p = std::lower_bound(f.begin(), f.end(), std::pair(v, x)) - f.begin();
s.rangeApply(p, p + 1, Tag(-(inf + x)));
s.rangeApply(p, m, Tag(1));
};
for (int i = 0; i < n; i++) {
add(i, a[i]);
}
for (int i = 0; i < Q; i++) {
rem(x[i], a[x[i]]);
a[x[i]] = v[i];
add(x[i], a[x[i]]);
answer[i] = s.info[1].x;
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
1436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
