Submission #100730

#	Time	Username	Problem	Language	Result	Execution time	Memory
100730		SpeedOfMagic	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4307 ms	93856 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct treap {
	treap *l = nullptr, *r = nullptr;
	int x, y, siz = 1, p;
	int c;
	int lazy = 0;
	int val;
	
	void pushdown() {
		if (l != nullptr) l -> lazy += lazy;
		if (r != nullptr) r -> lazy += lazy;
		val += lazy;
		c += lazy;
		lazy = 0;
	}
	
	void upd() {
		pushdown();
		if (l != nullptr) l -> pushdown();
		if (r != nullptr) r -> pushdown();
		siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
		val = max(c, max((l == nullptr) ? c : l -> val, (r == nullptr) ? c : r -> val));
	}
	
	treap(int a, int pp, int cc) : x(a), y(rng()), p(pp), c(cc) {val = c;}
};

int siz(treap *t) { return (t == nullptr) ? 0 : t -> siz; }

treap *arr;

treap* merge(treap *t1, treap *t2) {
	if (t1 == nullptr)
		return t2;
	if (t2 == nullptr)
		return t1;
	t1 -> pushdown();
	t2 -> pushdown();
	if (t1 -> y > t2 -> y) {
		t1 -> r = merge(t1 -> r, t2);
		t1 -> upd();
		return t1;
	} else {
		t2 -> l = merge(t1, t2 -> l);
		t2 -> upd();
		return t2;
	}
}

pair<treap*, treap*> split(treap *t, int x, int pos) {
	if (t == nullptr)
		return {nullptr, nullptr};
	t -> pushdown();
	if (t -> x > x || (t -> x == x && t -> p >= pos)) {
		auto tmp = split(t -> l, x, pos);
		t -> l = tmp.second;
		t -> upd();
		return {tmp.first, t};
	} else {
		auto tmp = split(t -> r, x, pos);
		t -> r = tmp.first;
		t -> upd();
		return {t, tmp.second};
	}
}

inline void addAll(treap *t, int a) { if (t != nullptr) t -> lazy += a; }

treap *root;

void prnt(treap *t) {
	if (t == nullptr)
		return;
	prnt(t -> l);
	cout << t -> x << t -> p << " ";
	prnt(t -> r);
}


vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	int n = A.size();
	pair<int, int> B[n];
	for (int i = 0; i < n; i++)
		B[i] = {A[i], i};
	sort(B, B + n);
	
	for (int i = 0; i < n; i++) 
		root = merge(root, new treap(B[i].fs, B[i].sc, B[i].sc - i));
	
	vector<int> answer(X.size());
	for (unsigned int query = 0; query < X.size(); query++) {
		int pos = X[query], val = V[query];
		if (A[pos] > val) {
			//a.fs -end position of element- b.fs -this element- th.sc
			auto a = split(root, val, pos);
			auto b = split(a.sc, A[pos], pos);
			auto th = split(b.sc, A[pos], pos + 1);
			addAll(b.fs, -1);
			treap *d = new treap(val, pos, pos - siz(a.fs));
			root = merge(merge(a.fs, d), merge(b.fs, th.sc));
		} else {
			//a.fs -this element- b.fs -end position of element- b.sc
			auto a = split(root, A[pos], pos);
			auto th = split(a.sc, A[pos], pos + 1);
			auto b = split(th.sc, val, pos);
			addAll(b.fs, 1);
			treap *d = new treap(val, pos, pos - siz(a.fs) - siz(b.fs));
			root = merge(merge(a.fs, b.fs), merge(d, b.sc));
		}
		
		A[pos] = val;
		root -> pushdown();
		answer[query] = root -> val;
		
		//prnt(root); cout << endl;
	}
		
	return answer;
}
/* 1 2
4 2
1 2 3 4
0 3
2 1
*//* 3 3 0
4 3
4 3 2 1
1 4
2 4
3 4
*/

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