#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
struct Tag {
int add;
Tag(int _add) : add(_add) {}
Tag() : add(0) {}
void apply(Tag &tag) { add += tag.add; }
};
struct Info {
int len, sum;
Info(int _len, int _sum) : len(_len), sum(_sum) {}
Info() : len(0), sum(0) {}
void apply(Tag &tag) { sum += tag.add * len; }
Info combine(Info &other) { return {len + other.len, sum + other.sum}; }
};
struct Tree {
vector<Tag> tag;
vector<Info> info;
Tree(int size) {
tag.resize(size*4);
info.resize(size*4);
}
void build(vector<Info> &base, int x, int xl, int xr) {
if (xl == xr) {
info[x] = base[xl];
} else {
int xm = (xl + xr) / 2;
build(base, x*2, xl, xm);
build(base, x*2+1, xm+1, xr);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
void pushdown(int x) {
info[x].apply(tag[x]);
if (x*2 < (int) tag.size()) tag[x*2].apply(tag[x]);
if (x*2+1 < (int) tag.size()) tag[x*2+1].apply(tag[x]);
tag[x] = {};
}
void update(int l, int r, int x, int xl, int xr, Tag delta) {
if (l > r) return;
pushdown(x);
if (l == xl && r == xr) {
tag[x].apply(delta);
} else {
int xm = (xl + xr) / 2;
update(l, min(r, xm), x*2, xl, xm, delta);
update(max(l, xm+1), r, x*2+1, xm+1, xr, delta);
pushdown(x); pushdown(x*2); pushdown(x*2+1);
info[x] = info[x*2].combine(info[x*2+1]);
}
}
Info query(int l, int r, int x, int xl, int xr) {
if (l > r) return {};
pushdown(x);
if (l == xl && r == xr) {
return info[x];
} else {
int xm = (xl + xr) / 2;
Info left = query(l, min(r, xm), x*2, xl, xm);
Info right = query(max(l, xm+1), r, x*2+1, xm+1, xr);
return left.combine(right);
}
}
};
// need to only query from a number if it is smaller than everything
// to the right of it
// i.e. pick the rightmost item, then the next smallest and next and so on
// if it is smaller than everything to the right, then i can
// count the number of items above it and subtract it from how much stuff is
// on the right, to get it ans
// in other words, this can be done if we use a segment tree to count number below x
// we can update one of these important values
// now we just need to be able to identify and track how these values change
// for now let's just see if i can get 60 points
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
int N = A.size();
int Q = X.size();
set<int> AV;
for (int a : A) AV.insert(a);
for (int v : V) AV.insert(v);
map<int,int> idxmap; int T = 0;
for (int av : AV) idxmap[av] = T++;
Tree tree(T);
vector<Info> base(T, {1, 0});
tree.build(base, 1, 0, T-1);
vector<set<int>> idx(T);
for (int i=0; i<N; i++) {
A[i] = idxmap[A[i]];
idx[A[i]].insert(i);
tree.update(0, A[i], 1, 0, T-1, {+1});
}
vector<int> ans(Q);
for (int i=0; i<Q; i++) {
idx[A[X[i]]].erase(X[i]);
tree.update(0, A[X[i]], 1, 0, T-1, {-1});
A[X[i]] = idxmap[V[i]];
tree.update(0, A[X[i]], 1, 0, T-1, {+1});
idx[A[X[i]]].insert(X[i]);
int prev = 0;
for (int j=0; j<T-1; j++) {
if (idx[j].empty()) continue;
int k = *idx[j].rbegin();
if (k < prev) continue;
ans[i] = max(ans[i], tree.query(j+1, j+1, 1, 0, T-1).sum - (T-1 - k));
prev = k;
}
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
1884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
