Submission #1012319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012319		d4xn	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1281 ms	91736 KiB

bubblesort2

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

#define all(x) x.begin(), x.end()

const int N = 5e5, inf = 1e9;

int n, q, a[N], x[N], v[N], seg[2][N*8], laz[N*8];
vector<int> b, ans;
vector<pair<int, int>> comp;

void pushDown(int p) {
	for (int h : {p*2, p*2+1}) {
		seg[0][h] += laz[p];
		laz[h] += laz[p];
	}
	laz[p] = 0;
}

void updateSet(int idx, int x, int p=1, int l=0, int r=n+q-1) {
	if (l == r) {
		seg[0][p] = x;
		if (x == -inf) seg[1][p] = 0;
		else seg[1][p] = 1;
		return;
	}
	pushDown(p);
	int mid = (l+r) >> 1;

	if (idx <= mid) updateSet(idx, x, p*2, l, mid);
	else updateSet(idx, x, p*2+1, mid+1, r);

	seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
	seg[1][p] = seg[1][p*2] + seg[1][p*2+1];
}

void updateSum(int idx, int x, int p=1, int l=0, int r=n+q-1) {
	if (idx <= l) {
		seg[0][p] += x;
		laz[p] += x;
		return;
	}
	pushDown(p);
	int mid = (l+r) >> 1;

	if (idx <= mid) updateSum(idx, x, p*2, l, mid);
	updateSum(idx, x, p*2+1, mid+1, r);

	seg[0][p] = max(seg[0][p*2], seg[0][p*2+1]);
	seg[1][p] = seg[1][p*2] + seg[1][p*2+1];
}

int queryCount(int idx, int p=1, int l=0, int r=n+q-1) {
	if (r <= idx) {
		return seg[1][p];
	}
	pushDown(p);
	int mid = (l+r) >> 1;

	int x = queryCount(idx, p*2, l, mid);
	if (mid+1 <= idx) x += queryCount(idx, p*2+1, mid+1, r);

	return x;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n = A.size();
	q = X.size();

	comp.resize(n+q);
	for (int i = 0; i < n; i++) {
		a[i] = A[i];
		comp[i] = make_pair(a[i], i);
	}

	for (int i = 0; i < q; i++) {
		x[i] = X[i];
		v[i] = V[i];
		comp[n+i] = make_pair(v[i], x[i]);
	}
	sort(all(comp));
	comp.erase(unique(all(comp)), comp.end());

	b.resize(n);
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(all(comp), make_pair(a[i], i)) - comp.begin();
		b[i] = a[i];
	}
	sort(all(b));

	for (int i = 0; i < q; i++) {
		v[i] = lower_bound(all(comp), make_pair(v[i], x[i])) - comp.begin();
	}

	memset(seg, 0, sizeof(seg));
	memset(laz, 0, sizeof(laz));
	for (int i = 0; i < n; i++) {
		int idx = lower_bound(all(b), a[i]) - b.begin();
		updateSet(a[i], i - idx);
	}

	ans.resize(q);
	for (int i = 0; i < q; i++) {//cerr << i << " a" << endl;
		// quito a[x[i]]
		updateSum(a[x[i]], 1);
		//cerr << i << " aa" << endl;
		updateSet(a[x[i]], -inf);
//cerr << i << " b" << endl;
		// añado v[i]
		int idx = queryCount(v[i]);
		updateSum(v[i], -1);
		updateSet(v[i], x[i] - idx);
//cerr << i << " c" << endl;
		ans[i] = seg[0][1];
		//cerr << i << " d" << endl;
		a[x[i]] = v[i];
	}

	return ans;
}

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