답안 #70330 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70330	2018-08-22T15:45:28 Z	fallingstar	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3277 ms	142052 KB

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.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	31736 KB	Output is correct
2	Correct	30 ms	31932 KB	Output is correct
3	Correct	33 ms	32072 KB	Output is correct
4	Correct	39 ms	32324 KB	Output is correct
5	Correct	39 ms	32324 KB	Output is correct
6	Correct	37 ms	32384 KB	Output is correct
7	Correct	41 ms	32432 KB	Output is correct
8	Correct	43 ms	32500 KB	Output is correct
9	Correct	39 ms	32548 KB	Output is correct
10	Correct	33 ms	32628 KB	Output is correct
11	Correct	35 ms	32668 KB	Output is correct
12	Correct	32 ms	32752 KB	Output is correct
13	Correct	36 ms	32792 KB	Output is correct
14	Correct	40 ms	32832 KB	Output is correct
15	Correct	36 ms	32884 KB	Output is correct
16	Correct	33 ms	32912 KB	Output is correct
17	Correct	33 ms	32952 KB	Output is correct
18	Correct	36 ms	32952 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	31736 KB	Output is correct
2	Correct	30 ms	31932 KB	Output is correct
3	Correct	33 ms	32072 KB	Output is correct
4	Correct	39 ms	32324 KB	Output is correct
5	Correct	39 ms	32324 KB	Output is correct
6	Correct	37 ms	32384 KB	Output is correct
7	Correct	41 ms	32432 KB	Output is correct
8	Correct	43 ms	32500 KB	Output is correct
9	Correct	39 ms	32548 KB	Output is correct
10	Correct	33 ms	32628 KB	Output is correct
11	Correct	35 ms	32668 KB	Output is correct
12	Correct	32 ms	32752 KB	Output is correct
13	Correct	36 ms	32792 KB	Output is correct
14	Correct	40 ms	32832 KB	Output is correct
15	Correct	36 ms	32884 KB	Output is correct
16	Correct	33 ms	32912 KB	Output is correct
17	Correct	33 ms	32952 KB	Output is correct
18	Correct	36 ms	32952 KB	Output is correct
19	Correct	45 ms	33880 KB	Output is correct
20	Correct	60 ms	34248 KB	Output is correct
21	Correct	53 ms	34416 KB	Output is correct
22	Correct	49 ms	34616 KB	Output is correct
23	Correct	58 ms	34684 KB	Output is correct
24	Correct	46 ms	34844 KB	Output is correct
25	Correct	57 ms	35008 KB	Output is correct
26	Correct	48 ms	35360 KB	Output is correct
27	Correct	46 ms	35360 KB	Output is correct
28	Correct	51 ms	35484 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	35484 KB	Output is correct
2	Correct	63 ms	36376 KB	Output is correct
3	Correct	90 ms	37700 KB	Output is correct
4	Correct	101 ms	38268 KB	Output is correct
5	Correct	101 ms	38976 KB	Output is correct
6	Correct	101 ms	39412 KB	Output is correct
7	Correct	100 ms	39960 KB	Output is correct
8	Correct	83 ms	40696 KB	Output is correct
9	Correct	85 ms	41136 KB	Output is correct
10	Correct	86 ms	41856 KB	Output is correct
11	Correct	75 ms	42512 KB	Output is correct
12	Correct	105 ms	43276 KB	Output is correct
13	Correct	96 ms	43740 KB	Output is correct
14	Correct	112 ms	44192 KB	Output is correct
15	Correct	79 ms	44868 KB	Output is correct
16	Correct	87 ms	45500 KB	Output is correct
17	Correct	82 ms	46092 KB	Output is correct
18	Correct	78 ms	46772 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	31736 KB	Output is correct
2	Correct	30 ms	31932 KB	Output is correct
3	Correct	33 ms	32072 KB	Output is correct
4	Correct	39 ms	32324 KB	Output is correct
5	Correct	39 ms	32324 KB	Output is correct
6	Correct	37 ms	32384 KB	Output is correct
7	Correct	41 ms	32432 KB	Output is correct
8	Correct	43 ms	32500 KB	Output is correct
9	Correct	39 ms	32548 KB	Output is correct
10	Correct	33 ms	32628 KB	Output is correct
11	Correct	35 ms	32668 KB	Output is correct
12	Correct	32 ms	32752 KB	Output is correct
13	Correct	36 ms	32792 KB	Output is correct
14	Correct	40 ms	32832 KB	Output is correct
15	Correct	36 ms	32884 KB	Output is correct
16	Correct	33 ms	32912 KB	Output is correct
17	Correct	33 ms	32952 KB	Output is correct
18	Correct	36 ms	32952 KB	Output is correct
19	Correct	45 ms	33880 KB	Output is correct
20	Correct	60 ms	34248 KB	Output is correct
21	Correct	53 ms	34416 KB	Output is correct
22	Correct	49 ms	34616 KB	Output is correct
23	Correct	58 ms	34684 KB	Output is correct
24	Correct	46 ms	34844 KB	Output is correct
25	Correct	57 ms	35008 KB	Output is correct
26	Correct	48 ms	35360 KB	Output is correct
27	Correct	46 ms	35360 KB	Output is correct
28	Correct	51 ms	35484 KB	Output is correct
29	Correct	49 ms	35484 KB	Output is correct
30	Correct	63 ms	36376 KB	Output is correct
31	Correct	90 ms	37700 KB	Output is correct
32	Correct	101 ms	38268 KB	Output is correct
33	Correct	101 ms	38976 KB	Output is correct
34	Correct	101 ms	39412 KB	Output is correct
35	Correct	100 ms	39960 KB	Output is correct
36	Correct	83 ms	40696 KB	Output is correct
37	Correct	85 ms	41136 KB	Output is correct
38	Correct	86 ms	41856 KB	Output is correct
39	Correct	75 ms	42512 KB	Output is correct
40	Correct	105 ms	43276 KB	Output is correct
41	Correct	96 ms	43740 KB	Output is correct
42	Correct	112 ms	44192 KB	Output is correct
43	Correct	79 ms	44868 KB	Output is correct
44	Correct	87 ms	45500 KB	Output is correct
45	Correct	82 ms	46092 KB	Output is correct
46	Correct	78 ms	46772 KB	Output is correct
47	Correct	645 ms	75188 KB	Output is correct
48	Correct	3050 ms	129816 KB	Output is correct
49	Correct	2924 ms	141728 KB	Output is correct
50	Correct	2710 ms	141896 KB	Output is correct
51	Correct	2944 ms	142052 KB	Output is correct
52	Correct	3277 ms	142052 KB	Output is correct
53	Correct	2671 ms	142052 KB	Output is correct
54	Correct	2685 ms	142052 KB	Output is correct
55	Correct	2661 ms	142052 KB	Output is correct
56	Correct	2472 ms	142052 KB	Output is correct
57	Correct	2594 ms	142052 KB	Output is correct
58	Correct	2454 ms	142052 KB	Output is correct
59	Correct	2033 ms	142052 KB	Output is correct
60	Correct	2230 ms	142052 KB	Output is correct
61	Correct	2239 ms	142052 KB	Output is correct
62	Correct	2171 ms	142052 KB	Output is correct
63	Correct	2069 ms	142052 KB	Output is correct
64	Correct	2196 ms	142052 KB	Output is correct
65	Correct	1767 ms	142052 KB	Output is correct
66	Correct	1781 ms	142052 KB	Output is correct
67	Correct	1891 ms	142052 KB	Output is correct

답안 #70330

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 40.0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
40.0 / 40.0