Submission #58072

#	Time	Username	Problem	Language	Result	Execution time	Memory
58072		memikakizaki	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	5027 ms	49840 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define all(a) begin(a), end(a)
#define csz(a) (int) a.size()
#define fori(i, a, b) for(int i = (int) a; i <= (int) b; ++i)
#define rofi(i, b, a) for(int i = (int) b; i >= (int) a; --i)
#define foreach(tt, a) for(auto &tt: a)
#define long long long
const int INF = 1e9+1;
const long MOD = 1e9+7, LINF = 1e16+1;
 
mt19937 eng;
uniform_int_distribution<> uintd;

struct node {
	node *l, *r;
	pair<int,int> key;
	int prior, cnt;
	int val, agg, lz;
	node(pair<int,int> key, int val): key(key), val(val) {
		l = NULL, r = NULL;
		prior = uintd(eng), cnt = 1;
		agg = val;
		lz = 0;
	}
};
using pnode = node*;

void apply(pnode t) {
	if(!t || t->lz == 0) return;
	t->agg += t->lz;
	t->val += t->lz;
	if(t->l) t->l->lz += t->lz;
	if(t->r) t->r->lz += t->lz;
	t->lz = 0;
}

void update(pnode t) {
	if(!t) return;
	apply(t->l), apply(t->r);
	t->cnt = 1;
	t->agg = t->val;
	if(t->l) t->agg = max(t->l->agg, t->agg), t->cnt += t->l->cnt;
	if(t->r) t->agg = max(t->r->agg, t->agg), t->cnt += t->r->cnt;
}

void split(pnode t, pnode &l, pnode &r, pair<int,int> targ) {
	apply(t);
	if(!t) return void(l = r = NULL);
	if(targ < t->key) split(t->l, l, t->l, targ), r = t; // equal goes left
	else split(t->r, t->r, r, targ), l = t;
	update(t);
}

void merge(pnode& t, pnode l, pnode r) {
	apply(l), apply(r);
	if(!l || !r) return void(t = (l ? l : r));
	if(l->prior > r->prior) merge(l->r, l->r, r), t = l;
	else merge(r->l, l, r->l), t = r;
	update(t);
}

void insert(pnode& t, pair<int,int> key, int val) {
	pnode lf, rg;
	split(t, lf, rg, key);
	merge(t, lf, new node(key, val));
	merge(t, t, rg);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	eng = mt19937(0);
	pnode root = NULL;
	vector<pair<int,int> > B;
	fori(i, 0, csz(A)-1) B.epb(A[i], i);
	sort(all(B));
	fori(i, 0, csz(B)-1) {
		insert(root, B[i], B[i].second - i);
	}

	vector<int> res(csz(X));
	fori(i, 0, csz(X)-1) {
		auto val1 = mp(A[X[i]], X[i]);
		auto val1_less = mp(A[X[i]], X[i]-1);
		auto val2 = mp(V[i], X[i]);
		
		pnode p1, p2, p3;
		split(root, p2, p3, val1);
		split(p2, p1, p2, val1_less);
		if(p3) ++p3->lz;
		merge(root, p1, p3);
		delete p2;
		
		split(root, p1, p2, val2);
		if(p2) --p2->lz;
		insert(p1, val2, val2.second - (p1 ? p1->cnt : 0));
		merge(root, p1, p2);

		A[X[i]] = V[i];
		res[i] = root->agg;
	}
	return res;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40