oj.uz

Submission #67182

# Submission time Handle Problem Language Result Execution time Memory
67182 2018-08-13T13:53:18 Z radoslav11 Bubble Sort 2 (JOI18_bubblesort2) C++14
100 / 100
 6929 ms 99628 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"
//#include "Lgrader.cpp"

using namespace std;
template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const int MAXN = (1 << 20);

static int q, n;

random_device rd;
mt19937 mt(rd());

struct node
{
	int sz, prior, value, answer, lazy;
	pair<int, int> v;
	node *l, *r;

	node()
	{
		prior = value = sz = answer = lazy = 0;
		l = r = nullptr;
	}

	node(int vv, int x)
	{
		v = {vv, x};
		value = answer = x;
		l = r = nullptr;
		prior = mt();
		lazy = 0;
		sz = 1;
	}
};

using pnode = node*;

inline int size(pnode t) { return t ? t->sz : 0; }

void push(pnode &t)
{
	if(!t) return;
	if(!t->lazy) return;
	
	t->answer += t->lazy;
	t->value += t->lazy;

	if(t->l) t->l->lazy += t->lazy;
	if(t->r) t->r->lazy += t->lazy;

	t->lazy = 0;
}

void pull(pnode &t)
{
	if(!t) return;

	push(t->l);
	push(t->r);

	t->sz = 1 + size(t->l) + size(t->r);

	t->answer = t->value;
	if(t->l) chkmax(t->answer, t->l->answer);
	if(t->r) chkmax(t->answer, t->r->answer);
}

void merge(pnode &t, pnode l, pnode r)
{
	push(l), push(r);
	if(!l) { t = r; return; }
	if(!r) { t = l; return; }

	if(l->prior > r->prior)
		merge(l->r, l->r, r), t = l;
	else
		merge(r->l, l, r->l), t = r;

	pull(t);
}

void split(pnode t, pnode &l, pnode &r, pair<int, int> k)
{
	push(t);
	if(!t) { l = r = nullptr; return; }

	if(t->v <= k)
		split(t->r, t->r, r, k), l = t;
	else
		split(t->l, l, t->l, k), r = t;

	pull(t);
}

void split_sz(pnode t, pnode &l, pnode &r, int k, int add = 0)
{
	push(t);
	if(!t) { l = r = nullptr; return; }

	int idx = add + size(t->l);
	if(idx <= k)
		split_sz(t->r, t->r, r, k, idx + 1), l = t;
	else
		split_sz(t->l, l, t->l, k, add), r = t;

	pull(t);
}


pnode root;

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V)
{
	q = X.size();
	n = A.size();
	std::vector<int> answer(q);

	for(int i = 0; i < n; i++)
	{
		pnode l, r, nw = new node(A[i], i);
		
		split(root, l, r, {A[i], i});

		nw->value -= size(l);
		nw->answer -= size(l);
		if(r) r->lazy--;

		merge(root, l, nw);
		merge(root, root, r);
	}

	for(int i = 0; i < q; i++)
	{
		int x = X[i], v = V[i];
		
		pnode l, r, mid;
	
		split(root, l, r, {A[x], x - 1});
		split_sz(r, mid, r, 0);
		
		if(r) r->lazy += 1;
		
		merge(root, l, r);
	
		split(root, l, r, {v, x});
		mid->v = {v, x};
		
		mid->value = mid->answer = x - size(l);
		
		if(r) r->lazy -= 1;

		merge(root, l, mid);
		merge(root, root, r);

		answer[i] = root->answer;
	
		A[x] = v;
	}

	return answer;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 10 ms 824 KB Output is correct
4 Correct 13 ms 824 KB Output is correct
5 Correct 10 ms 868 KB Output is correct
6 Correct 10 ms 884 KB Output is correct
7 Correct 11 ms 1056 KB Output is correct
8 Correct 11 ms 1144 KB Output is correct
9 Correct 13 ms 1264 KB Output is correct
10 Correct 12 ms 1264 KB Output is correct
11 Correct 12 ms 1264 KB Output is correct
12 Correct 14 ms 1280 KB Output is correct
13 Correct 10 ms 1324 KB Output is correct
14 Correct 11 ms 1368 KB Output is correct
15 Correct 11 ms 1400 KB Output is correct
16 Correct 10 ms 1440 KB Output is correct
17 Correct 11 ms 1480 KB Output is correct
18 Correct 13 ms 1520 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 10 ms 824 KB Output is correct
4 Correct 13 ms 824 KB Output is correct
5 Correct 10 ms 868 KB Output is correct
6 Correct 10 ms 884 KB Output is correct
7 Correct 11 ms 1056 KB Output is correct
8 Correct 11 ms 1144 KB Output is correct
9 Correct 13 ms 1264 KB Output is correct
10 Correct 12 ms 1264 KB Output is correct
11 Correct 12 ms 1264 KB Output is correct
12 Correct 14 ms 1280 KB Output is correct
13 Correct 10 ms 1324 KB Output is correct
14 Correct 11 ms 1368 KB Output is correct
15 Correct 11 ms 1400 KB Output is correct
16 Correct 10 ms 1440 KB Output is correct
17 Correct 11 ms 1480 KB Output is correct
18 Correct 13 ms 1520 KB Output is correct
19 Correct 38 ms 2200 KB Output is correct
20 Correct 49 ms 2496 KB Output is correct
21 Correct 40 ms 2688 KB Output is correct
22 Correct 42 ms 2884 KB Output is correct
23 Correct 41 ms 3024 KB Output is correct
24 Correct 42 ms 3272 KB Output is correct
25 Correct 50 ms 3492 KB Output is correct
26 Correct 53 ms 3560 KB Output is correct
27 Correct 41 ms 3728 KB Output is correct
28 Correct 38 ms 3884 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 5192 KB Output is correct
2 Correct 170 ms 6824 KB Output is correct
3 Correct 375 ms 8632 KB Output is correct
4 Correct 364 ms 9136 KB Output is correct
5 Correct 349 ms 9652 KB Output is correct
6 Correct 346 ms 10260 KB Output is correct
7 Correct 362 ms 10840 KB Output is correct
8 Correct 390 ms 11420 KB Output is correct
9 Correct 334 ms 12000 KB Output is correct
10 Correct 200 ms 12732 KB Output is correct
11 Correct 216 ms 13364 KB Output is correct
12 Correct 190 ms 13996 KB Output is correct
13 Correct 157 ms 14748 KB Output is correct
14 Correct 173 ms 15320 KB Output is correct
15 Correct 168 ms 15964 KB Output is correct
16 Correct 134 ms 16608 KB Output is correct
17 Correct 151 ms 17172 KB Output is correct
18 Correct 207 ms 17880 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 508 KB Output is correct
3 Correct 10 ms 824 KB Output is correct
4 Correct 13 ms 824 KB Output is correct
5 Correct 10 ms 868 KB Output is correct
6 Correct 10 ms 884 KB Output is correct
7 Correct 11 ms 1056 KB Output is correct
8 Correct 11 ms 1144 KB Output is correct
9 Correct 13 ms 1264 KB Output is correct
10 Correct 12 ms 1264 KB Output is correct
11 Correct 12 ms 1264 KB Output is correct
12 Correct 14 ms 1280 KB Output is correct
13 Correct 10 ms 1324 KB Output is correct
14 Correct 11 ms 1368 KB Output is correct
15 Correct 11 ms 1400 KB Output is correct
16 Correct 10 ms 1440 KB Output is correct
17 Correct 11 ms 1480 KB Output is correct
18 Correct 13 ms 1520 KB Output is correct
19 Correct 38 ms 2200 KB Output is correct
20 Correct 49 ms 2496 KB Output is correct
21 Correct 40 ms 2688 KB Output is correct
22 Correct 42 ms 2884 KB Output is correct
23 Correct 41 ms 3024 KB Output is correct
24 Correct 42 ms 3272 KB Output is correct
25 Correct 50 ms 3492 KB Output is correct
26 Correct 53 ms 3560 KB Output is correct
27 Correct 41 ms 3728 KB Output is correct
28 Correct 38 ms 3884 KB Output is correct
29 Correct 68 ms 5192 KB Output is correct
30 Correct 170 ms 6824 KB Output is correct
31 Correct 375 ms 8632 KB Output is correct
32 Correct 364 ms 9136 KB Output is correct
33 Correct 349 ms 9652 KB Output is correct
34 Correct 346 ms 10260 KB Output is correct
35 Correct 362 ms 10840 KB Output is correct
36 Correct 390 ms 11420 KB Output is correct
37 Correct 334 ms 12000 KB Output is correct
38 Correct 200 ms 12732 KB Output is correct
39 Correct 216 ms 13364 KB Output is correct
40 Correct 190 ms 13996 KB Output is correct
41 Correct 157 ms 14748 KB Output is correct
42 Correct 173 ms 15320 KB Output is correct
43 Correct 168 ms 15964 KB Output is correct
44 Correct 134 ms 16608 KB Output is correct
45 Correct 151 ms 17172 KB Output is correct
46 Correct 207 ms 17880 KB Output is correct
47 Correct 1367 ms 28468 KB Output is correct
48 Correct 5498 ms 56836 KB Output is correct
49 Correct 6173 ms 74268 KB Output is correct
50 Correct 6151 ms 74268 KB Output is correct
51 Correct 6025 ms 74308 KB Output is correct
52 Correct 6308 ms 74308 KB Output is correct
53 Correct 6929 ms 74308 KB Output is correct
54 Correct 5807 ms 74308 KB Output is correct
55 Correct 6073 ms 74308 KB Output is correct
56 Correct 5482 ms 74308 KB Output is correct
57 Correct 6134 ms 74308 KB Output is correct
58 Correct 5284 ms 74308 KB Output is correct
59 Correct 4815 ms 74308 KB Output is correct
60 Correct 5161 ms 74308 KB Output is correct
61 Correct 4890 ms 76352 KB Output is correct
62 Correct 4372 ms 76372 KB Output is correct
63 Correct 4737 ms 76372 KB Output is correct
64 Correct 4540 ms 86796 KB Output is correct
65 Correct 4285 ms 98004 KB Output is correct
66 Correct 4338 ms 99628 KB Output is correct
67 Correct 4319 ms 99628 KB Output is correct