oj.uz

답안 #69819

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69819 2018-08-21T14:48:39 Z fallingstar Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 36 ms 32856 KB 
#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 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, n - 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]] = V[i];
		int new_idx = GetIndex(V[i]);

		while (!pos[old_idx].empty() && A[pos[old_idx].top()] != old_val) pos[old_idx].pop();
		segtree.Modify(old_idx, 1);

		pos[new_idx].push(X[i]);
		segtree.Modify(new_idx, -1);

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

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 31736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 31736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 32856 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 33 ms 31736 KB Output isn't correct
2 Halted 0 ms 0 KB -