Submission #651132

#	Time	Username	Problem	Language	Result	Execution time	Memory
651132		rsjw	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1866 ms	62792 KiB

bubblesort2

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 5;
int maxn[MAXN * 4 + 10], lazy[MAXN * 4 + 10];

void pushup(int rt) { maxn[rt] = max(maxn[rt << 1], maxn[rt << 1 | 1]); }
void pushdown(int rt) {
	if (lazy[rt]) {
		maxn[rt << 1] += lazy[rt], maxn[rt << 1 | 1] += lazy[rt];
		lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
		lazy[rt] = 0;
	}
}
void update(int L, int R, int I, int l = 1, int r = MAXN, int rt = 1) {
	if (L <= l && r <= R) {
		maxn[rt] += I, lazy[rt] += I;
		return;
	}
	int m = (l + r) / 2;
	pushdown(rt);
	if (L <= m)
		update(L, R, I, l, m, rt << 1);
	if (R > m)
		update(L, R, I, m + 1, r, rt << 1 | 1);
	pushup(rt);
}
int query(int L, int R, int l = 1, int r = MAXN, int rt = 1) {
	if (L <= l && r <= R)
		return maxn[rt];
	int m = (l + r) / 2, ans = -1e9, placed = 0;
	pushdown(rt);
	if (L <= m) {
		ans = query(L, R, l, m, rt << 1);
		placed = 1;
	}
	if (R > m) {
		if(placed) ans = max(ans, query(L, R, m + 1, r, rt << 1 | 1));
		else ans = query(L, R, m + 1, r, rt << 1 | 1);
	}
	return ans;
}
void p_update(int x, int I, int len = MAXN) {
	int v = query(x, x);
	update(x, x, I - v);
}

typedef pair<int, int> pr;
#define mp make_pair
pr pool[MAXN];
int tot;

struct BIT {
	int t[MAXN + 20];
	void update(int x, int I) {
		while (x <= MAXN)
			t[x] += I, x += x & -x;
	}
	int query(int x) {
		int ans = 0;
		while (x)
			ans += t[x], x -= x & -x;
		return ans;
	}
} T;

void compress(int &x, int id) {
	x = lower_bound(pool + 1, pool + tot + 1, mp(x, id)) - pool;
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X,
                            std::vector<int> V) {
	int Q = X.size(), N = A.size();
	std::vector<int> answer(Q);
	for (int i = 0; i < N; i++)
		pool[++tot] = mp(A[i], i);
	for (int i = 0; i < Q; i++)
		pool[++tot] = mp(V[i], X[i]);
	sort(pool + 1, pool + tot + 1);
	tot = unique(pool + 1, pool + tot + 1) - pool - 1;
	// for (i = 1; i <= tot; i++) {
	// 	printf("%d %d\n",pool[i].first,pool[i].second);
	// }
	for (int i = 0; i < N; i++)
		compress(A[i], i), T.update(A[i], 1);
	for (int i = 0; i < Q; i++)
		compress(V[i], X[i]);
	for (int i = 0; i < 4 * MAXN + 10; i++)
		maxn[i] = -1e7;
	for (int i = 0; i < N; i++) {
		p_update(A[i], i - T.query(A[i] - 1));
		// cerr<<"ID"<<A[i]<<"EXPECTED"<<i - T.query(A[i] - 1)<<endl;
	}

	// cerr << "Compressed Results:" << endl;
	// for (int i = 0; i < N; i++)
	// 	cerr << A[i] << " \n"[i == N - 1];
	// for (int i = 0; i < Q; i++)
	// 	cerr << X[i] << " " << V[i] << endl;

	for (int i = 0; i < Q; i++) {
		int src = A[X[i]];

		// cerr << "SGT - before:" << endl;
		// for (int i = 1; i <= 7; i++)
		// 	cerr << query(i, i) << " \n"[i == 7];

		if (src == V[i]) {
			answer[i] = query(1, MAXN);
			continue;
		}
		T.update(src, -1);
		T.update(V[i], 1);
		p_update(src, -1e7);
		p_update(V[i], X[i] - T.query(V[i] - 1));

		if (src < V[i]) {
			if (src + 1 <= V[i] - 1)
				update(src + 1, V[i] - 1, 1);
		} else {
			if (V[i] + 1 <= src - 1)
				update(V[i] + 1, src - 1, -1);
		}
		A[X[i]] = V[i];
		answer[i] = query(1, MAXN);
	}
	return answer;
}

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