| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1097815 | michified | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 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.
#include <bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define lid id * 2 + 1
#define rid id * 2 + 2
#define lmn LLONG_MIN
#define lmx LLONG_MAX
#define imn ll_MIN
#define imx ll_MAX
using namespace std;
const ll mod = 1e9 + 7;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag, tree_order_statistics_node_update>
ll n;
// query # elems segtree implementation begins here
vector<ordered_set> ste; // segment tree elems
void builde(vector<ll>& a, ll id, ll l, ll r) {
if (l == r) {
ste[id].insert(a[l]);
return;
}
ll mid = (l + r) / 2;
builde(a, lid, l, mid);
builde(a, rid, mid + 1, r);
for (ll elem : ste[lid]) ste[id].insert(elem);
for (ll elem : ste[rid]) ste[id].insert(elem);
}
ll querye(ll id, ll l, ll r, ll pos, ll val) {
if (pos < l) return 0;
if (r <= pos) return ste[id].order_of_key(val);
ll mid = (l + r) / 2;
return querye(lid, l, mid, pos, val) + querye(rid, mid + 1, r, pos, val);
}
void updatee(ll id, ll l, ll r, ll pos, ll old, ll cur) {
if (l == r) {
ste[id].clear();
ste[id].insert(cur);
return;
}
ll mid = (l + r) / 2;
if (pos <= mid) updatee(lid, l, mid, pos, old, cur);
else updatee(rid, mid + 1, r, pos, old, cur);
ste[id].erase(old);
ste[id].insert(cur);
}
// query # elems segtree implementation ends here
// ... //
// query min element segtree implementation begins here
vector<ll> stmin;
void build(vector<ll>& a, ll id, ll l, ll r) {
if (l == r) {
stmin[id] = a[l];
return;
}
ll mid = (l + r) / 2;
build(a, lid, l, mid);
build(a, rid, mid + 1, r);
stmin[id] = min(stmin[lid], stmin[rid]);
}
ll querym(ll id, ll l, ll r, ll val) {
if (stmin[id] > val) return l;
if (l == r) return l + 1;
ll mid = (l + r) / 2;
ll res = querym(rid, mid + 1, r, val);
if (res == mid + 1) return querym(lid, l, mid, val);
return res;
}
void updatem(ll id, ll l, ll r, ll pos, ll val) {
if (l == r) {
stmin[id] = val;
return;
}
ll mid = (l + r) / 2;
if (pos <= mid) updatem(lid, l, mid, pos, val);
else updatem(rid, mid + 1, r, pos, val);
stmin[id] = min(stmin[lid], stmin[rid]);
}
// query min element segtree implementation ends here
// ... //
// query ans segtree implementation begins here
vector<ll> st, lazy;
void build(vector<ll>& a, ll id, ll l, ll r) {
if (l == r) {
st[id] = a[l];
return;
}
ll mid = (l + r) / 2;
build(a, lid, l, mid);
build(a, rid, mid + 1, r);
st[id] = max(st[lid], st[rid]);
}
void pd(ll id, ll l, ll mid, ll r) {
st[lid] += lazy[id];
st[rid] += lazy[id];
lazy[lid] += lazy[id];
lazy[rid] += lazy[id];
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll ul, ll val) {
if (r < ul) return;
if (l >= ul) {
st[id] += val;
lazy[id] += val;
return;
}
ll mid = (l + r) / 2;
pd(id, l, mid, r);
update(lid, l, mid, ul, val);
update(rid, mid + 1, r, ul, val);
st[id] = max(st[lid], st[rid]);
}
void clazy(ll id, ll l, ll r, ll pos, ll val) {
if (l == r) {
st[id] = l - querye(0, 0, n - 1, pos - 1, val);
return;
}
ll mid = (l + r) / 2;
pd(id, l, mid, r);
if (pos <= mid) clazy(lid, l, mid, pos, val);
else clazy(rid, mid + 1, r, pos, val);
st[id] = max(st[lid], st[rid]);
}
void replace(vector<ll>& a, ll pos, ll val) {
update(0, 0, n - 1, querym(0, 0, n - 1, a[pos]), 1);
updatem(0, 0, n - 1, pos, val);
updatee(0, 0, n - 1, pos, a[pos], val);
a[pos] = val;
update(0, 0, n - 1, querym(0, 0, n - 1, val), -1);
clazy(0, 0, n - 1, pos, val);
}
void init(vector<ll>& a) {
st.resize(n * 4);
lazy.resize(n * 4);
vector<ll> inp(n);
for (ll i = 0; i < n; i++) inp[i] = i - querye(0, 0, n - 1, i - 1, a[i]);
build(inp, 0, 0, n - 1);
}
// query ans segtree implementations ends here
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
ll q = X.size(), i;
vector<ll> a(n);
for (i = 0; i < n; i++) a[i] = A[i] * 1000000ll + i;
stmin.resize(n * 4);
ste.resize(n * 4);
build(a, 0, 0, n - 1);
builde(a, 0, 0, n - 1);
init(a);
vector<int> ans(q);
for (i = 0; i < q; i++) {
replace(a, X[i], V[i] * 1000000ll + X[i]);
ans[i] = st[0];
}
return ans;
}