Submission #163512

#	Time	Username	Problem	Language	Result	Execution time	Memory
163512		NachoLibre	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	56 ms	4596 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#include "bubblesort2.h"

struct dor {
	dor *l, *r;
	int dt, sh;
	dor() {
		l = r = NULL;
		dt = sh = 0;
	}

	int sd() {
		return dt + sh;
	}

	void sheps() {
		if(l == NULL) l = new dor();
		if(r == NULL) r = new dor();
		l->sh += sh;
		r->sh += sh;
		sh = 0;
	}

	void pump() {
		dt = max(l->sd(), r->sd());
	}
} *rt = new dor();

void gnk(int l, int r, int sl, int sr, int vl, dor *&t) {
	if(l > sr || r < sl) return;
	if(l >= sl && r <= sr) {
		t->sh += vl;
		return;
	}
	t->sheps();
	gnk(l, (l + r) / 2, sl, sr, vl, t->l);
	gnk((l + r) / 2 + 1, r, sl, sr, vl, t->r);
	t->pump();
}

int rwi(int l, int r, int si, dor *&t) {
	if(l == r) return t->sd();
	if((l + r) / 2 >= si) return rwi(l, (l + r) / 2, si, t->l);
	return rwi((l + r) / 2 + 1, r, si, t->r);
}

const int inf = 100000000;

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v) {
	int n = a.size();
	int q = x.size();
	vector<int> fp;
	vector<pair<int, int> > u;
	map<pair<int, int>, int> ma;
	for(int i = 0; i < n; ++i) {
		u.push_back({a[i], i});
	}
	for(int i = 0; i < q; ++i) {
		--x[i];
		u.push_back({v[i], x[i]});
	}
	sort(u.begin(), u.end());
	for(int i = 0; i < n + q; ++i) {
		ma[u[i]] = i + 1;
	}
	gnk(1, n + q, 1, n + q, -inf, rt);
	for(int i = 0; i < n; ++i) {
		int rae = ma[{a[i], i}];
		gnk(1, n + q, rae, rae, inf + i, rt);
		gnk(1, n + q, rae + 1, n + q, -1, rt);
	}
	int rvu;
	//for(int j = 1; j <= n + q; ++j) cout << rwi(1, n + q, j, rt) << " ";
	//cout << endl;
	for(int i = 0; i < q; ++i) {
		int sdn = ma[{a[x[i]], x[i]}], sad = ma[{v[i], x[i]}];
		//cout << sdn << " " << sad << endl;
		rvu = 1;
		a[x[i]] = v[i];
		gnk(1, n + q, sdn, sdn, -inf - x[i], rt);
		gnk(1, n + q, sad, sad, inf + x[i], rt);
		if(sdn > sad) swap(sdn, sad), rvu = -1;
		//gnk(1, n + q, sdn, sdn, -inf - x[i], rt);
		if(sad - sdn >= 2) gnk(1, n + q, sdn + 1, sad - 1, rvu, rt);
		//gnk(1, n + q, sad, sad, inf + x[i], rt);
		int tp = rt->sd();
		fp.push_back(tp);
		//for(int j = 1; j <= n + q; ++j) cout << rwi(1, n + q, j, rt) << " ";
		//cout << endl;
	}
	return fp;
}

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