This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int N = 5e5, inf = 1e9;
int n, q, a[N], x[N], v[N], seg[2][N*8], laz[N*8];
vector<int> b, ans;
vector<pair<int, int>> comp;
void pushDown(int p) {
for (int h : {p*2, p*2+1}) {
seg[0][h] += laz[p];
laz[h] += laz[p];
}
laz[p] = 0;
}
void updateSet(int idx, int x, int p=1, int l=0, int r=n+q-1) {
if (l == r) {
seg[0][p] = x;
if (x == -inf) seg[1][p] = 0;
else seg[1][p] = 1;
return;
}
pushDown(p);
int mid = (l+r) >> 1;
if (idx <= mid) updateSet(idx, x, p*2, l, mid);
else updateSet(idx, x, p*2+1, mid+1, r);
seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
seg[1][p] = seg[1][p*2] + seg[1][p*2+1];
}
void updateSum(int idx, int x, int p=1, int l=0, int r=n+q-1) {
if (idx <= l) {
seg[0][p] += x;
laz[p] += x;
return;
}
pushDown(p);
int mid = (l+r) >> 1;
if (idx <= mid) updateSum(idx, x, p*2, l, mid);
updateSum(idx, x, p*2+1, mid+1, r);
seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
seg[1][p] = seg[1][p*2] + seg[1][p*2+1];
}
int queryCount(int idx, int p=1, int l=0, int r=n+q-1) {
if (r <= idx) {
return seg[1][p];
}
pushDown(p);
int mid = (l+r) >> 1;
int x = queryCount(idx, p*2, l, mid);
if (mid+1 <= idx) x += queryCount(idx, p*2+1, mid+1, r);
return x;
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
q = X.size();
comp.resize(n+q);
for (int i = 0; i < n; i++) {
a[i] = A[i];
comp[i] = make_pair(a[i], i);
}
for (int i = 0; i < q; i++) {
x[i] = X[i];
v[i] = V[i];
comp[n+i] = make_pair(v[i], x[i]);
}
sort(all(comp));
comp.erase(unique(all(comp)), comp.end());
b.resize(n);
for (int i = 0; i < n; i++) {
a[i] = lower_bound(all(comp), make_pair(a[i], i)) - comp.begin();
b[i] = a[i];
}
sort(all(b));
for (int i = 0; i < q; i++) {
v[i] = lower_bound(all(comp), make_pair(v[i], x[i])) - comp.begin();
}
memset(seg, 0, sizeof(seg));
memset(laz, 0, sizeof(laz));
for (int i = 0; i < n; i++) {
int idx = lower_bound(all(b), a[i]) - b.begin();
updateSet(a[i], i - idx);
}
ans.resize(q);
for (int i = 0; i < q; i++) {
updateSum(a[x[i]], 1);
updateSet(a[x[i]], -inf);
int idx = queryCount(v[i]);
updateSum(v[i], -1);
updateSet(v[i], x[i] - idx);
ans[i] = seg[0][1];
a[x[i]] = v[i];
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |