| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 171383 | kuroni | 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 <iostream>
#include <cstdio>
#include <random>
using namespace std;
const int N = 5E5 + 5, INF = 2E9 + 7;
random_device rd;
mt19937 rng(rd());
uniform_int_distribution<int> dis(0, INF);
int n, q, u, v, a[N];
long long cur = 0;
struct STreap;
int get(STreap *cur);
struct STreap
{
int val, sz, pri;
STreap *l, *r;
STreap(int _val, int _pri, STreap *_l, STreap *_r)
{
val = _val;
pri = _pri;
l = _l;
r = _r;
sz = get(l) + get(r) + 1;
}
} *rt = nullptr;
int get(STreap *cur)
{
return cur == nullptr ? 0 : cur->sz;
}
STreap *upd(STreap *cur, STreap *l, STreap *r)
{
*cur = STreap(cur->val, cur->pri, l, r);
return cur;
}
pair<STreap *, STreap *> split(STreap *cur, long long v)
{
if (cur == nullptr)
return make_pair(nullptr, nullptr);
pair<STreap *, STreap *> mid;
if (cur->val < v)
{
mid = split(cur->r, v);
return make_pair(upd(cur, cur->l, mid.first), mid.second);
}
else
{
mid = split(cur->l, v);
return make_pair(mid.first, upd(cur, mid.second, cur->r));
}
}
STreap *merge(STreap *l, STreap *r)
{
if (l == nullptr)
return r;
if (r == nullptr)
return l;
if (l->pri > r->pri)
return upd(l, l->l, merge(l->r, r));
else
return upd(r, merge(l, r->l), r->r);
}
STreap *insert(STreap *cur, STreap *x)
{
if (cur == nullptr)
return x;
if (x == nullptr)
return cur;
pair<STreap *, STreap *> mid = split(cur, x->val);
return merge(merge(mid.first, x), mid.second);
}
STreap *erase(STreap *cur, int x)
{
pair<STreap *, STreap *> mid = split(cur, x);
if (mid.second == nullptr)
return mid.first;
else
return merge(merge(mid.first, mid.second->l), mid.second->r);
}
class CTree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1
private:
STreap *tr[4 * N];
public:
void build(int l, int r, int i)
{
tr[i] = nullptr;
for (int x = l; x <= r; x++)
tr[i] = insert(tr[i], new STreap(a[l], dis(rng), nullptr, nullptr));
if (l == r)
return;
build(l, m, lc);
build(m + 1, r, rc);
}
void upd(int l, int r, int i, int u, int v)
{
tr[i] = erase(tr[i], a[u]);
tr[i] = insert(tr[i], new STreap(v, dis(rng), nullptr, nullptr));
if (l == r)
return;
if (u <= m)
upd(l, m, lc, u, v);
else
upd(m + 1, r, rc, u, v);
}
int que(int l, int r, int i, int L, int R, int v, bool le)
{
if (l > R || r < L)
return 0;
if (L <= l && r <= R)
{
pair<STreap *, STreap *> mid = split(tr[i], v);
int tmp = get(le ? mid.first : mid.second);
tr[i] = merge(mid.first, mid.second);
return tmp;
}
return que(l, m, lc, L, R, v, le) + que(m + 1, r, rc, L, R, v, le);
}
#undef m
#undef lc
#undef rc
} seg;
std::vector<long long> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V)
{
std::vector<long long> ans;
int n = A.size();
int q = X.size();
for (int i = 1; i <= n; i++)
a[i] = A[i - 1];
seg.build(1, n, 1);
for (int i = 2; i <= n; i++)
cur += seg.que(1, n, 1, 1, i - 1, a[i], true);
for (int i = 1; i <= q; i++)
{
u = X[i - 1] + 1;
v = V[i - 1];
if (u != 1)
{
cur -= seg.que(1, n, 1, 1, u - 1, a[u], true);
cur += seg.que(1, n, 1, 1, u - 1, v, true);
}
if (u != n)
{
cur -= seg.que(1, n, 1, u + 1, n, a[u] + 1, false);
cur += seg.que(1, n, 1, u + 1, n, v + 1, false);
}
seg.upd(1, n, 1, u, v);
a[u] = v;
ans.push_back(cur);
}
return ans;
}