Submission #70330

#	Time	Username	Problem	Language	Result	Execution time	Memory
70330		fallingstar	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3277 ms	142052 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e6 + 2;
const int INF = 1 << 30;

int m;
int allValues[N];
priority_queue<int> pos[N];

struct TSegmentTree
{
	#define lc id * 2 + 1
	#define rc id * 2 + 2
	#define mid (sl + sr) / 2
	int node[1 << 21], lazy[1 << 21], cnt[1 << 21];
	void Propagate(int id, int sl, int sr)
	{
		if (lazy[id] != 0)
		{
			node[id] += lazy[id];
			if (sl < sr)
				lazy[lc] += lazy[id], lazy[rc] += lazy[id];
			lazy[id] = 0;
		}
	}
	void Build(int id, int sl, int sr, int pref)
	{
		if (sl < sr)
		{
			Build(lc, sl, mid, pref);
			Build(rc, mid + 1, sr, pref + cnt[lc]);
			node[id] = max(node[lc], node[rc]);
			cnt[id] = cnt[lc] + cnt[rc];
		}
		else
			if (pos[sl].empty()) node[id] = -INF, cnt[id] = 0;
			else cnt[id] = pos[sl].size(), node[id] = pos[sl].top() - (pref + cnt[id]) + 1;
	}
	void Modify(int id, int sl, int sr, int u, int val, int pref)
	{
		Propagate(id, sl, sr);
		if (sl < sr)
		{
			if (u <= mid)
			{
				lazy[rc] += val;
				Propagate(rc, mid + 1, sr);
				Modify(lc, sl, mid, u, val, pref);
			}
			else
			{
				Propagate(lc, sl, mid);
				Modify(rc, mid + 1, sr, u, val, pref + cnt[lc]);
			}
			node[id] = max(node[lc], node[rc]);
			cnt[id] = cnt[lc] + cnt[rc];
		}
		else
			if (pos[sl].empty()) cnt[id] = 0, node[id] = -INF;
			else {cnt[id] += -val; node[id] = pos[sl].top() - (pref + cnt[id]) + 1;}
	}
	void Modify(int u, int val) { return Modify(0, 0, m - 1, u, val, 0); }
	int GetMax() { return node[0]; }
	#undef lc
	#undef rc
	#undef mid
} segtree;

int GetIndex(int x) { return lower_bound(allValues, allValues + m, x) - allValues; }

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) 
{
	int n = A.size();
	int q = X.size();
	copy(A.begin(), A.end(), allValues);
	copy(V.begin(), V.end(), allValues + n);

	m = n + q;
	sort(allValues, allValues + m);
	m = unique(allValues, allValues + m) - allValues;

	for (int i = 0; i < n; ++i)
		pos[GetIndex(A[i])].push(i);

	segtree.Build(0, 0, m - 1, 0);

	vector<int> answer(q);
	for (int i = 0; i < q; ++i)
	{
		int old_val = A[X[i]];
		int old_idx = GetIndex(old_val);

		A[X[i]] = 0;
		while (!pos[old_idx].empty() && A[pos[old_idx].top()] != old_val) pos[old_idx].pop();
		int new_idx = GetIndex(V[i]);

		segtree.Modify(old_idx, 1);

		A[X[i]] = V[i];
		pos[new_idx].push(X[i]);
		while (!pos[new_idx].empty() && A[pos[new_idx].top()] != V[i]) pos[new_idx].pop();
		segtree.Modify(new_idx, -1);

		answer[i] = segtree.GetMax();
	}
	return answer;
}

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