답안 #70327 :: oj.uz

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

bubblesort2

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

using namespace std;

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

int m;
int allValues[N];
set<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] = *prev(pos[sl].end()) - (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] = *prev(pos[sl].end()) - (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])].insert(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);

		pos[old_idx].erase(X[i]);
		int new_idx = GetIndex(V[i]);

		segtree.Modify(old_idx, 1);

		A[X[i]] = V[i];
		pos[new_idx].insert(X[i]);
		segtree.Modify(new_idx, -1);

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

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	45 ms	47484 KB	Output is correct
3	Correct	50 ms	47680 KB	Output is correct
4	Correct	55 ms	47744 KB	Output is correct
5	Correct	45 ms	47864 KB	Output is correct
6	Correct	48 ms	47904 KB	Output is correct
7	Correct	50 ms	47952 KB	Output is correct
8	Correct	54 ms	48060 KB	Output is correct
9	Correct	57 ms	48064 KB	Output is correct
10	Correct	54 ms	48180 KB	Output is correct
11	Correct	45 ms	48220 KB	Output is correct
12	Correct	52 ms	48300 KB	Output is correct
13	Correct	54 ms	48340 KB	Output is correct
14	Correct	49 ms	48436 KB	Output is correct
15	Correct	55 ms	48604 KB	Output is correct
16	Correct	47 ms	48644 KB	Output is correct
17	Correct	49 ms	48644 KB	Output is correct
18	Correct	54 ms	48644 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	45 ms	47484 KB	Output is correct
3	Correct	50 ms	47680 KB	Output is correct
4	Correct	55 ms	47744 KB	Output is correct
5	Correct	45 ms	47864 KB	Output is correct
6	Correct	48 ms	47904 KB	Output is correct
7	Correct	50 ms	47952 KB	Output is correct
8	Correct	54 ms	48060 KB	Output is correct
9	Correct	57 ms	48064 KB	Output is correct
10	Correct	54 ms	48180 KB	Output is correct
11	Correct	45 ms	48220 KB	Output is correct
12	Correct	52 ms	48300 KB	Output is correct
13	Correct	54 ms	48340 KB	Output is correct
14	Correct	49 ms	48436 KB	Output is correct
15	Correct	55 ms	48604 KB	Output is correct
16	Correct	47 ms	48644 KB	Output is correct
17	Correct	49 ms	48644 KB	Output is correct
18	Correct	54 ms	48644 KB	Output is correct
19	Correct	65 ms	49596 KB	Output is correct
20	Correct	62 ms	49764 KB	Output is correct
21	Correct	68 ms	49980 KB	Output is correct
22	Correct	71 ms	50212 KB	Output is correct
23	Correct	59 ms	50348 KB	Output is correct
24	Correct	62 ms	50512 KB	Output is correct
25	Correct	66 ms	50720 KB	Output is correct
26	Correct	84 ms	50920 KB	Output is correct
27	Correct	66 ms	51004 KB	Output is correct
28	Correct	63 ms	51160 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	66 ms	51852 KB	Output is correct
2	Correct	131 ms	53584 KB	Output is correct
3	Correct	193 ms	55204 KB	Output is correct
4	Correct	181 ms	55772 KB	Output is correct
5	Correct	185 ms	56468 KB	Output is correct
6	Correct	155 ms	56916 KB	Output is correct
7	Correct	192 ms	57588 KB	Output is correct
8	Correct	186 ms	58076 KB	Output is correct
9	Correct	190 ms	58784 KB	Output is correct
10	Correct	126 ms	59364 KB	Output is correct
11	Correct	144 ms	60020 KB	Output is correct
12	Correct	135 ms	60680 KB	Output is correct
13	Correct	162 ms	61336 KB	Output is correct
14	Correct	130 ms	61980 KB	Output is correct
15	Correct	131 ms	62628 KB	Output is correct
16	Correct	115 ms	63268 KB	Output is correct
17	Correct	114 ms	63904 KB	Output is correct
18	Correct	120 ms	64556 KB	Output is correct

Subtask #4
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47352 KB	Output is correct
2	Correct	45 ms	47484 KB	Output is correct
3	Correct	50 ms	47680 KB	Output is correct
4	Correct	55 ms	47744 KB	Output is correct
5	Correct	45 ms	47864 KB	Output is correct
6	Correct	48 ms	47904 KB	Output is correct
7	Correct	50 ms	47952 KB	Output is correct
8	Correct	54 ms	48060 KB	Output is correct
9	Correct	57 ms	48064 KB	Output is correct
10	Correct	54 ms	48180 KB	Output is correct
11	Correct	45 ms	48220 KB	Output is correct
12	Correct	52 ms	48300 KB	Output is correct
13	Correct	54 ms	48340 KB	Output is correct
14	Correct	49 ms	48436 KB	Output is correct
15	Correct	55 ms	48604 KB	Output is correct
16	Correct	47 ms	48644 KB	Output is correct
17	Correct	49 ms	48644 KB	Output is correct
18	Correct	54 ms	48644 KB	Output is correct
19	Correct	65 ms	49596 KB	Output is correct
20	Correct	62 ms	49764 KB	Output is correct
21	Correct	68 ms	49980 KB	Output is correct
22	Correct	71 ms	50212 KB	Output is correct
23	Correct	59 ms	50348 KB	Output is correct
24	Correct	62 ms	50512 KB	Output is correct
25	Correct	66 ms	50720 KB	Output is correct
26	Correct	84 ms	50920 KB	Output is correct
27	Correct	66 ms	51004 KB	Output is correct
28	Correct	63 ms	51160 KB	Output is correct
29	Correct	66 ms	51852 KB	Output is correct
30	Correct	131 ms	53584 KB	Output is correct
31	Correct	193 ms	55204 KB	Output is correct
32	Correct	181 ms	55772 KB	Output is correct
33	Correct	185 ms	56468 KB	Output is correct
34	Correct	155 ms	56916 KB	Output is correct
35	Correct	192 ms	57588 KB	Output is correct
36	Correct	186 ms	58076 KB	Output is correct
37	Correct	190 ms	58784 KB	Output is correct
38	Correct	126 ms	59364 KB	Output is correct
39	Correct	144 ms	60020 KB	Output is correct
40	Correct	135 ms	60680 KB	Output is correct
41	Correct	162 ms	61336 KB	Output is correct
42	Correct	130 ms	61980 KB	Output is correct
43	Correct	131 ms	62628 KB	Output is correct
44	Correct	115 ms	63268 KB	Output is correct
45	Correct	114 ms	63904 KB	Output is correct
46	Correct	120 ms	64556 KB	Output is correct
47	Correct	728 ms	89032 KB	Output is correct
48	Correct	2736 ms	137256 KB	Output is correct
49	Correct	3001 ms	154688 KB	Output is correct
50	Correct	3323 ms	167564 KB	Output is correct
51	Correct	3038 ms	180436 KB	Output is correct
52	Correct	3256 ms	193264 KB	Output is correct
53	Correct	3478 ms	205724 KB	Output is correct
54	Correct	2650 ms	218132 KB	Output is correct
55	Correct	2919 ms	229768 KB	Output is correct
56	Correct	2973 ms	240984 KB	Output is correct
57	Correct	3452 ms	252236 KB	Output is correct
58	Correct	3242 ms	262980 KB	Output is correct
59	Correct	2705 ms	272464 KB	Output is correct
60	Correct	2839 ms	281972 KB	Output is correct
61	Correct	2563 ms	291284 KB	Output is correct
62	Correct	2039 ms	300440 KB	Output is correct
63	Correct	2167 ms	309332 KB	Output is correct
64	Correct	2308 ms	318088 KB	Output is correct
65	Correct	2148 ms	327788 KB	Output is correct
66	Correct	2039 ms	336272 KB	Output is correct
67	Correct	2021 ms	343252 KB	Output is correct

답안 #70327

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