Submission #1120009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120009		Thunnus	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1738 ms	62796 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 (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));
	}
	for (int i = 0; i < Q; i++) {
		int src = A[X[i]];
		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