Submission #1163076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163076		pinbu	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1438 ms	108784 KiB

bubblesort2

#include "bubblesort2.h"
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int lazy[1 << 21], val[1 << 21];
void update(int Lf, int Rt, int x, int id, int l, int r) {
	if (Lf <= l && r <= Rt) {
		val[id] += x;
		lazy[id] += x;
		return;
	}
	
	int mid = l + r >> 1;
	if (Lf <= mid) update(Lf, Rt, x, id << 1, l, mid);
	if (Rt > mid) update(Lf, Rt, x, id << 1 | 1, mid + 1, r);
	val[id] = max(val[id << 1], val[id << 1 | 1]) + lazy[id];
}
void update(int Lf, int Rt, int x) {
	if (Lf <= Rt) {
		update(Lf, Rt, x, 1, 0, 999999);
	}
}
set<int> se[1000000];

std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
	int N = a.size(), Q = x.size();
	std::vector<int> answer(Q);
	vector<int> comp;
	for (int ai: a) {
		comp.emplace_back(ai);
	}
	for (int vi: v) {
		comp.emplace_back(vi);
	}
	sort(begin(comp), end(comp));
	comp.resize(unique(begin(comp), end(comp)) - comp.begin());
	int nnn = comp.size();
	vector<int> cnt(nnn, 0);
	for (int i = N - 1; i >= 0; i--) {
		a[i] = lower_bound(begin(comp), end(comp), a[i]) - comp.begin();
		if (!cnt[a[i]]) {
			update(a[i], a[i], i + 1);
		}
		se[a[i]].insert(i + 1);
		cnt[a[i]]++;
	}
	for (int p = 0; p < nnn; p++) {
		if (cnt[p]) {
			update(p, nnn - 1, -cnt[p]);
		}
	}
	for (int &vi: v) {
		vi = lower_bound(begin(comp), end(comp), vi) - comp.begin();
	}
	
	
	auto upd = [&] (int t, int p) {
		int xnxx = a[p];
		update(xnxx, nnn - 1, -t);
	};
	for (int i = 0; i < Q; i++) {
		int p = x[i], xnxx = v[i];
		
		upd(-1, p);
		int vl = -*se[a[p]].rbegin();
		se[a[p]].erase(p + 1);
		if (se[a[p]].size()) {
			vl += *se[a[p]].rbegin();
		}
		update(a[p], a[p], vl);
		a[p] = xnxx;
		upd(1, p);
		vl = 0;
		if (se[a[p]].size()) vl = -*se[a[p]].rbegin();
		se[a[p]].insert(p + 1);
		vl += *se[a[p]].rbegin();
		update(a[p], a[p], vl);
		answer[i] = val[1];
	}	
	return answer;
}
////////////////////////////////////

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