Submission #222819

#	Time	Username	Problem	Language	Result	Execution time	Memory
222819		PeppaPig	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	677 ms	49364 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

#define var int p = 1, int l = 0, int r = coord.size() - 1
#define mid ((l + r) >> 1)
#define lb p << 1, l, mid
#define rb p << 1 | 1, mid + 1, r

const int N = 1 << 19;

int n, q;
int t[N << 1], lz[N << 1];
vector<pii> coord;

int get(pii x) { return lower_bound(coord.begin(), coord.end(), x) - coord.begin(); }

void push(var) {
	if(lz[p]) {
		t[p] += lz[p];
		if(l != r) lz[p << 1] += lz[p], lz[p << 1 | 1] += lz[p];
		lz[p] = 0;
	}
}

void update(int x, int y, int k, var) {
	push(p, l, r);
	if(x > r || l > y) return;
	if(x <= l && r <= y) {
		lz[p] += k, push(p, l, r);
		return;
	}
	update(x, y, k, lb), update(x, y, k, rb);
	t[p] = max(t[p << 1], t[p << 1 | 1]);
}

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

	for(int i = 0; i < n; i++) coord.emplace_back(A[i], i);
	for(int i = 0; i < q; i++) coord.emplace_back(V[i], X[i]);

	sort(coord.begin(), coord.end());
	coord.resize(unique(coord.begin(), coord.end()) - coord.begin());

	function<void(int, int)> add = [&](int i, int coef) {
		int idx1 = get(pii(A[i], i));
		update(idx1, idx1, (i + 1) * coef);
		int idx2 = get(pii(A[i], -1));
		update(idx2, coord.size() - 1, -coef);
	};

	vector<int> ans;
	for(int i = 0; i < n; i++) add(i, 1);
	for(int i = 0; i < q; i++) {
		add(X[i], -1);
		A[X[i]] = V[i];
		add(X[i], 1);
		ans.emplace_back(t[1]);
	}

	return ans;
}

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