Submission #651110

#	Time	Username	Problem	Language	Result	Execution time	Memory
651110		rsjw	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	36 ms	32076 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] != -1e7) {
		maxn[rt << 1] += lazy[rt], maxn[rt << 1 | 1] += lazy[rt];
		lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
		lazy[rt] = -1e7;
	}
}
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;
	if (L <= m)
		ans = max(ans, query(L, R, l, m, rt << 1));
	if (R > m)
		ans = max(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, 1, len, 1);
	update(x, x, I - v, 1, len, 1);
}
int pool[MAXN], tot;

struct BIT {
	int t[MAXN + 5];
	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) { x = lower_bound(pool + 1, pool + tot + 1, x) - pool; }
std::vector<int> countScans(std::vector<int> A, std::vector<int> X,
                            std::vector<int> V) {
	int Q = X.size(), N = A.size();
	for (int i = 0; i < N; i++)
		A[i] *= 2;
	for (int i = 0; i < Q; i++)
		V[i] *= 2;
	std::vector<int> answer(Q);
	for (int i = 0; i < N; i++)
		A[i] += i, pool[++tot] = A[i];
	for (int i = 0; i < Q; i++)
		V[i] += X[i], pool[++tot] = V[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]), T.update(A[i], 1);
	for (int i = 0; i < Q; i++)
		compress(V[i]);
	for (int i = 0; i < 4 * MAXN + 5; i++)
		maxn[i] = lazy[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:" << endl;
		// for (int i = 1; i <= 6; i++)
		// 	cerr << query(i, i) << " \n"[i == 6];
		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: 0 / 17
• Subtask 2: 0 / 21
• Subtask 3: 0 / 22
• Subtask 4: 0 / 40