| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 363355 | buyolitsez | 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 "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define eb emplace_back
typedef long long ll;
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
const ll ADD = 1000000;
//const int MAXN = 5e5 + 15;
const int MAXN = 10;
const int MAXE = 1e6 + 15;
const int INF = 2139062143;
const int nINF = -2139062144;
struct Treap{
int key, prior, mx, add, inv, sz;
int left, right;
Treap(int k = 0, int i = 0) {
key = k;
prior = rnd();
mx = i;
add = 0;
sz = 1;
inv = i;
left = right = -1;
}
};
Treap t[MAXE];
int st[4 * MAXN];
int timer = 1;
int GetMx(int v) {
if (v == -1) {
return nINF;
}
return t[v].mx;
}
int GetSz(int v) {
if (v == -1) {
return 0;
}
return t[v].sz;
}
void Push(int v) {
if (v != -1 && t[v].add) {
t[v].inv += t[v].add;
t[v].mx += t[v].add;
if (t[v].left != -1) {
t[t[v].left].add += t[v].add;
}
if (t[v].right != -1) {
t[t[v].right].add += t[v].add;
}
t[v].add = 0;
}
}
void Update(int v) {
if (v != -1) {
t[v].mx = max({t[v].inv, GetMx(t[v].left), GetMx(t[v].right)});
t[v].sz = GetSz(t[v].left) + GetSz(t[v].right) + 1;
}
}
int Merge(int t1, int t2) {
Push(t1);
Push(t2);
if (t1 == -1) {return t2;}
if (t2 == -1) {return t1;}
if (t[t1].prior > t[t2].prior) {
t[t1].right = Merge(t[t1].right, t2);
Update(t1);
return t1;
}
t[t2].left = Merge(t1, t[t2].left);
Update(t2);
return t2;
}
pair <int, int> Split(int v, int k) {
if (v == -1) {return {-1, -1};}
if (t[v].key >= k) {
auto splited = Split(t[v].left, k);
t[v].left = splited.second;
Update(v);
return {splited.first, v};
} else {
auto splited = Split(t[v].right, k);
t[v].right = splited.first;
Update(v);
return {v, splited.second};
}
}
int MakeV(int key, int inv) {
t[timer] = Treap(key, inv);
return timer++;
}
int Insert(int v, int key, int inv) {
auto splited = Split(v, key);
int now = MakeV(key, inv);
v = Merge(Merge(splited.first, now), splited.second);
return v;
}
int HowManyMoreX(int l, int r, int x, int v = 0, int vl = 0, int vr = MAXN - 1) {
if (vl > r || vr < l) {return 0;}
if (vl >= l && vr <= r) {
auto splited = Split(st[v], x + 1);
int ans = GetSz(splited.second);
st[v] = Merge(splited.first, splited.second);
return ans;
}
int vm = vl + (vr - vl) / 2;
return HowManyMoreX(l, r, x, 2 * v + 1, vl, vm) + HowManyMoreX(l, r, x, 2 * v + 2, vm + 1, vr);
}
void InsertST(int pos, int key, int inv, int v = 0, int vl = 0, int vr = MAXN - 1) {
if (vl > pos || vr < pos) {return;}
if (st[v] == 0) {
st[v] = MakeV(key, inv);
} else {
st[v] = Insert(st[v], key, inv);
}
if (vl != vr) {
int vm = vl + (vr - vl) / 2;
InsertST(pos, key, inv, 2 * v + 1, vl, vm);
InsertST(pos, key, inv, 2 * v + 2, vm + 1, vr);
}
}
void AddInsersions(int l, int r, int x, int del, int v = 0, int vl = 0, int vr = MAXN - 1) {
if (r < vl || vr < l) {return;}
if (vl >= l && vr <= r) {
if (st[v] != 0) {
auto splited = Split(st[v], x);
if (splited.first != -1) {
t[splited.first].add += del;
}
st[v] = Merge(splited.first, splited.second);
}
return;
}
int vm = vl + (vr - vl) / 2ll;
}
void Insert(int i, int x) {
AddInversions(i + 1, MAXE - 1, x, 1);
int nowInv = HowManyMoreX(0, i - 1, x);
InsertST(i, x, nowInv);
}
void DeleteST(int i, int x, int v = 0, int vl = 0, int vr = MAXN - 1) {
if (vl > i || vr < i) {return;}
if (GetSz(st[v]) == 1) {
st[v] = 0;
} else {
auto splited = Split(st[v], x);
auto splited2 = Split(splited.second, x + 1);
st[v] = Merge(splited.first, splited2.second);
}
if (vl != vr) {
int vm = vl + (vr - vl) / 2;
DeleteST(i, x, 2 * v + 1, vl, vm);
DeleteST(i, x, 2 * v + 2, vm + 1, vr);
}
}
void Delete(int i, int x) {
DeleteST(i, x);
}
int GetAns(int v) {
Push(st[v]);
return GetMx(st[v]);
}
std::vector<int> countScans(std::vector<int> aa,std::vector<int> xx,std::vector<int> vv){
vector <ll> a, x, v;
for (auto u : aa) {
a.eb(u);
}
for (int i = 0; i < xx.size(); ++i) {
x.eb(xx[i]);
v.eb(vv[i]);
}
int n = a.size(), q = x.size();
vector <int> s(q, n - 1);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * ADD + i;
Insert(i, a[i]);
cout << GetAns(0) << '\n';
}
for(int f = 0; f < q; ++f) {
Delete(x[f], a[x[f]]);
Insert(x[f], v[f] * ADD + x[f]);
a[x[f]] = v[f] * ADD + x[f];
s[f] = GetAns(0);
}
return s;
}