Submission #100728

#	Time	Username	Problem	Language	Result	Execution time	Memory
100728		SpeedOfMagic	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	21 ms	2816 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();
		siz = ((l == nullptr) ? 0 : l -> siz) + ((r == nullptr) ? 0 : r -> siz) + 1;
		val = max(c, max((l == nullptr) ? 0 : l -> val, (r == nullptr) ? 0 : 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;
inline void ins(int a, int P, int c) {
	pair<treap*, treap*> p = split(root, a, P);
	root = merge(merge(p.fs, new treap(a, P, c)), p.sc);
}


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++) 
		ins(B[i].fs, B[i].sc, B[i].sc - i);
	
	vector<int> answer(X.size());
	for (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);
			root = merge(merge(a.fs, new treap(val, pos, pos - siz(a.fs))), 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);
			root = merge(merge(a.fs, b.fs), merge(new treap(val, pos, pos - siz(a.fs) - siz(b.fs)), b.sc));
		}
		
		A[pos] = val;
		answer[query] = root -> val;
	}
		
	return answer;
}
/* 1 2
4 2
1 2 3 4
0 3
2 1
*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:91:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int query = 0; query < X.size(); query++) {
                      ~~~~~~^~~~~~~~~~

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