# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
67181 | radoslav11 | Bubble Sort 2 (JOI18_bubblesort2) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "bubblesort2.h"
//#include "Lgrader.cpp"
using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);
static int q, n;
random_device rd;
mt19937 mt(rd());
struct node
{
int sz, prior, value, answer, lazy;
pair<int, int> v;
node *l, *r;
node()
{
prior = value = sz = answer = lazy = 0;
l = r = nullptr;
}
node(int vv, int x)
{
v = {vv, x};
value = answer = x;
l = r = nullptr;
prior = mt();
lazy = 0;
sz = 1;
}
};
using pnode = node*;
inline int size(pnode t) { return t ? t->sz : 0; }
void push(pnode &t)
{
if(!t) return;
if(!t->lazy) return;
t->answer += t->lazy;
t->value += t->lazy;
if(t->l) t->l->lazy += t->lazy;
if(t->r) t->r->lazy += t->lazy;
t->lazy = 0;
}
void pull(pnode &t)
{
if(!t) return;
push(t->l);
push(t->r);
t->sz = 1 + size(t->l) + size(t->r);
t->answer = t->value;
if(t->l) chkmax(t->answer, t->l->answer);
if(t->r) chkmax(t->answer, t->r->answer);
}
void merge(pnode &t, pnode l, pnode r)
{
push(l), push(r);
if(!l) { t = r; return; }
if(!r) { t = l; return; }
if(l->prior > r->prior)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
pull(t);
}
void split(pnode t, pnode &l, pnode &r, pair<int, int> k)
{
push(t);
if(!t) { l = r = nullptr; return; }
if(t->v <= k)
split(t->r, t->r, r, k), l = t;
else
split(t->l, l, t->l, k), r = t;
pull(t);
}
void split_sz(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
push(t);
if(!t) { l = r = nullptr; return; }
int idx = add + size(t->l);
if(idx <= k)
split_sz(t->r, t->r, r, k, idx + 1), l = t;
else
split_sz(t->l, l, t->l, k, add), r = t;
pull(t);
}
pnode root;
std::vector<int> count_scans(std::vector<int> A, std::vector<int> X, std::vector<int> V)
{
q = X.size();
n = A.size();
std::vector<int> answer(q);
for(int i = 0; i < n; i++)
{
pnode l, r, nw = new node(A[i], i);
split(root, l, r, {A[i], i});
nw->value -= size(l);
nw->answer -= size(l);
if(r) r->lazy--;
merge(root, l, nw);
merge(root, root, r);
}
for(int i = 0; i < q; i++)
{
int x = X[i], v = V[i];
pnode l, r, mid;
split(root, l, r, {A[x], x - 1});
split_sz(r, mid, r, 0);
if(r) r->lazy += 1;
merge(root, l, r);
split(root, l, r, {v, x});
mid->v = {v, x};
mid->value = mid->answer = x - size(l);
if(r) r->lazy -= 1;
merge(root, l, mid);
merge(root, root, r);
answer[i] = root->answer;
A[x] = v;
}
return answer;
}