oj.uz

Submission #70327

# Submission time Handle Problem Language Result Execution time Memory
70327 2018-08-22T15:41:19 Z fallingstar Bubble Sort 2 (JOI18_bubblesort2) C++17
100 / 100
 3478 ms 343252 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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