#include <bits/stdc++.h>
#include "bubblesort2.h"
#define bp __builtin_popcountll
#define pb push_back
#define in(s) freopen(s, "r", stdin);
#define inout(s, end1, end2) freopen((string(s) + "." + end1).c_str(), "r", stdin),\
freopen((string(s) + "." + end2).c_str(), "w", stdout);
#define fi first
#define se second
#define bw(i, r, l) for (int i = r - 1; i >= l; i--)
#define fw(i, l, r) for (int i = l; i < r; i++)
#define fa(i, x) for (auto i: x)
using namespace std;
const int mod = 1e9 + 7, inf = 1061109567;
const long long infll = 4557430888798830399;
const int N = 5e5 + 5;
int n, q;
struct Query {
int val, pos, id;
bool operator<(const Query &rhs) const {
return val == rhs.val ? id < rhs.id : val < rhs.val;
}
};
vector<Query> vec;
class SegTree {
private:
int mx[N << 3], cnt[N << 3], lazy[N << 3];
//cnt saves if a query is "active"
void build(int l, int r, int x) {
if (l == r) {
cnt[x] = 0;
mx[x] = -inf;
lazy[x] = 0;
return;
}
int m = (l + r) >> 1;
build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
cnt[x] = 0, mx[x] = -inf, lazy[x] = 0;
}
void push(int l, int r, int x) {
mx[x] += lazy[x];
if (l != r) {
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
}
lazy[x] = 0;
}
void add(int l, int r, int s, int e, int x, int val) {
push(l, r, x);
if (l > e || r < s) return;
if (s <= l && r <= e) {
lazy[x] += val;
push(l, r, x);
return;
}
int m = (l + r) >> 1;
add(l, m, s, e, x << 1, val), add(m + 1, r, s, e, x << 1 | 1, val);
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
void set(int l, int r, int pos, int mxval, int cntval, int x) {
push(l, r, x);
if (l > pos || r < pos) return;
if (l == r) {
mx[x] = mxval;
cnt[x] = cntval;
return;
}
int m = (l + r) >> 1;
set(l, m, pos, mxval, cntval, x << 1), set(m + 1, r, pos, mxval, cntval, x << 1 | 1);
cnt[x] = cnt[x << 1] + cnt[x << 1 | 1];
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
int get(int l, int r, int s, int e, int x) {
push(l, r, x);
if (l > e || r < s) return 0;
if (s <= l && r <= e) return cnt[x];
int m = (l + r) >> 1;
return get(l, m, s, e, x << 1) + get(m + 1, r, s, e, x << 1 | 1);
}
public:
int n;
void init(int _n) { n = _n; build(0, n - 1, 1); }
void add(int l, int r, int val) { add(0, n - 1, l, r, 1, val); }
int get(int l, int r) { return get(0, n - 1, l, r, 1); }
void set(int pos, int mxval, int cntval) { set(0, n - 1, pos, mxval, cntval, 1); }
int getans() { return mx[1]; }
} st;
int curid[N], realpos[N];
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
n = a.size(), q = x.size();
fw (i, 0, n) vec.pb({a[i], i, i});
fw (i, 0, q) vec.pb({v[i], x[i], i + n});
//Save segment tree of queries and the answer for the modified index within the query
st.init(n + q);
fw (i, 0, vec.size()) {
int pos = vec[i].pos, id = vec[i].id;
if (id >= n) realpos[id - n] = i;
else {
int tmp = pos - st.get(0, i);
curid[pos] = id;
st.set(i, tmp, 1);
//Don't need to lazy since queries are processed in order here
}
}
vector<int> res;
fw (i, 0, q) {
st.add(curid[x[i]], n + q - 1, 1);
st.set(curid[x[i]], -inf, 0);
curid[x[i]] = realpos[i];
int tmp = x[i] - st.get(0, realpos[i]);
st.add(curid[x[i]], n + q - 1, -1);
st.set(curid[x[i]], tmp, 1);
res.pb(st.getans());
}
return res;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:11:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fw(i, l, r) for (int i = l; i < r; i++)
bubblesort2.cpp:95:6:
fw (i, 0, vec.size()) {
~~~~~~~~~~~~~~~~
bubblesort2.cpp:95:2: note: in expansion of macro 'fw'
fw (i, 0, vec.size()) {
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
2008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
