| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 104915 | eriksuenderhauf | Bubble Sort 2 (JOI18_bubblesort2) | C++11 | 0 ms | 0 KiB |
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("O3")
#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
const int MAXN = 1e6 + 5;
const int INF = 1e9 + 7;
int cid[MAXN], B[MAXN];
int n = 0, q = 0;
oset ind;
pii arr[MAXN], C[MAXN];
int tre[MAXN * 4], lazy[MAXN * 4], updVal[MAXN];
void build(int l, int r, int k) {
lazy[k] = 0;
if (l == r) {
tre[k] = -INF;
return;
}
int m = (l + r) / 2;
build(l, m, k * 2);
build(m + 1, r, k * 2 + 1);
tre[k] = max(tre[k*2], tre[k*2+1]);
}
void upd(int l, int r, int k, int a, int b, int v, int fl) {
if (lazy[k] != 0) {
tre[k] += lazy[k];
if (l != r) {
lazy[k*2] += lazy[k];
lazy[k*2+1] += lazy[k];
}
lazy[k] = 0;
}
if (a > b)
return;
if (r < a || b < l)
return;
if (a <= l && r <= b) {
if (l == r && fl == 1)
tre[k] = v;
else
tre[k] += v;
if (l != r)
lazy[k*2] += v, lazy[k*2+1] += v;
return;
}
int m = (l + r) / 2;
upd(l, m, k*2, a, b, v, fl);
upd(m + 1, r, k*2+1, a, b, v, fl);
tre[k] = max(tre[k*2], tre[k*2+1]);
}
vi count_scans(vi A, vi X, vi V)
{
vi ans;
n = A.size(), q = X.size();
for (int i = 0; i < n; i++)
{
B[i] = A[i];
arr[i] = {A[i], i};
C[i] = arr[i];
ind.insert({A[i], i});
cid[i] = i;
}
sort(cid, cid + n, [&A](int l, int r) -> bool {
if (A[l] == A[r])
return l < r;
return A[l] < A[r];
});
for (int i = 0; i < q; i++) {
ind.erase({B[X[i]], X[i]});
B[X[i]] = V[i];
ind.insert({B[X[i]], X[i]});
int r = ind.order_of_key({B[X[i]], X[i]});
arr[i + n] = {B[X[i]], X[i]};
updVal[i + n] = X[i] - r;
}
for (int i = 0; i < n; i++) B[i] = A[i];
sort(arr, arr + n + q);
build(0, n + q - 1, 1);
sort(C, C + n);
for (int i = 0; i < n; i++) {
int l = lower_bound(arr, arr + n + q, C[i]) - arr;
upd(0, n + q - 1, 1, l, l, cid[i] - i, 1);
}
for (int i = n; i < n + q; i++) {
int l = lower_bound(arr, arr + n + q, mp(B[X[i-n]], X[i-n])) - arr;
B[X[i-n]] = V[i-n];
int r = lower_bound(arr, arr + n + q, mp(B[X[i-n]], X[i-n])) - arr;
upd(0, n + q - 1, 1, l, l, -INF, 1);
upd(0, n + q - 1, 1, r, r, updVal[i], 1);
if (l < r) upd(0, n + q - 1, 1, l + 1, r - 1, 1, 0);
else upd(0, n + q - 1, 1, r + 1, l - 1, -1, 0);
ans.pb(tre[1]);
}
return ans;
}