Submission #711834

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
711834	2023-03-17T14:56:14 Z	rainboy	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	5056 ms	52544 KB

bubblesort2

#include "bubblesort2.h"

using namespace std;

typedef vector<int> vi;

const int N = 500000, Q = 500000, N_ = N + Q + 1;

unsigned int Z = 12345;

int rand_() {
	return (Z *= 3) >> 1;
}

int aa[N];
int zz[N_ + 1], ll[N_ + 1], rr[N_ + 1], ii[N_ + 1], sz[N_ + 1], xx[N_ + 1], _, u_, l_, r_;

int node(int i) {
	static int _ = 1;

	zz[_] = rand_();
	ii[_] = i;
	sz[_] = 1;
	xx[_] = i + 1;
	return _++;
}

void pul(int u) {
	int l = ll[u], r = rr[u];

	sz[u] = sz[l] + 1 + sz[r];
	xx[u] = max(max(xx[l], ii[u]) + 1 + sz[r], xx[r]);
}

void split(int u, int i) {
	int c;

	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	c = aa[ii[u]] != aa[i] ? aa[ii[u]] - aa[i] : ii[u] - i;
	if (c < 0) {
		split(rr[u], i);
		rr[u] = l_, l_ = u;
	} else if (c > 0) {
		split(ll[u], i);
		ll[u] = r_, r_ = u;
	} else {
		u_ = u, l_ = ll[u], r_ = rr[u];
		ll[u] = rr[u] = 0;
	}
	pul(u);
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v), pul(u);
		return u;
	} else {
		ll[v] = merge(u, ll[v]), pul(v);
		return v;
	}
}

void tr_add(int i) {
	split(u_, i);
	u_ = merge(merge(l_, node(i)), r_);
}

void tr_remove(int i) {
	split(u_, i);
	u_ = merge(l_, r_);
}

vi countScans(vi aa_, vi ii, vi bb) {
	int n = aa_.size();
	for (int i = 0; i < n; i++)
		aa[i] = aa_[i];
	for (int i = 0; i < n; i++)
		tr_add(i);
	int q = ii.size();
	vi ans(q);
	for (int h = 0; h < q; h++) {
		int i = ii[h], b = bb[h];
		tr_remove(i);
		aa[i] = b;
		tr_add(i);
		ans[h] = xx[u_] - n;
	}
	return ans;
}

Subtask #1
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	3 ms	480 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	5 ms	544 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	476 KB	Output is correct
8	Correct	4 ms	480 KB	Output is correct
9	Correct	4 ms	476 KB	Output is correct
10	Correct	3 ms	476 KB	Output is correct
11	Correct	4 ms	480 KB	Output is correct
12	Correct	3 ms	484 KB	Output is correct
13	Correct	3 ms	536 KB	Output is correct
14	Correct	3 ms	448 KB	Output is correct
15	Correct	3 ms	436 KB	Output is correct
16	Correct	3 ms	440 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	472 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	3 ms	480 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	5 ms	544 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	476 KB	Output is correct
8	Correct	4 ms	480 KB	Output is correct
9	Correct	4 ms	476 KB	Output is correct
10	Correct	3 ms	476 KB	Output is correct
11	Correct	4 ms	480 KB	Output is correct
12	Correct	3 ms	484 KB	Output is correct
13	Correct	3 ms	536 KB	Output is correct
14	Correct	3 ms	448 KB	Output is correct
15	Correct	3 ms	436 KB	Output is correct
16	Correct	3 ms	440 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	472 KB	Output is correct
19	Correct	14 ms	1004 KB	Output is correct
20	Correct	15 ms	1084 KB	Output is correct
21	Correct	15 ms	1144 KB	Output is correct
22	Correct	17 ms	1116 KB	Output is correct
23	Correct	14 ms	1104 KB	Output is correct
24	Correct	15 ms	1052 KB	Output is correct
25	Correct	14 ms	1156 KB	Output is correct
26	Correct	15 ms	1092 KB	Output is correct
27	Correct	14 ms	1120 KB	Output is correct
28	Correct	13 ms	1088 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	21 ms	1412 KB	Output is correct
2	Correct	70 ms	3040 KB	Output is correct
3	Correct	132 ms	4792 KB	Output is correct
4	Correct	138 ms	4828 KB	Output is correct
5	Correct	128 ms	4804 KB	Output is correct
6	Correct	130 ms	4812 KB	Output is correct
7	Correct	130 ms	4780 KB	Output is correct
8	Correct	145 ms	4832 KB	Output is correct
9	Correct	122 ms	4796 KB	Output is correct
10	Correct	80 ms	4896 KB	Output is correct
11	Correct	84 ms	4824 KB	Output is correct
12	Correct	83 ms	4824 KB	Output is correct
13	Correct	73 ms	4828 KB	Output is correct
14	Correct	82 ms	4792 KB	Output is correct
15	Correct	66 ms	4808 KB	Output is correct
16	Correct	53 ms	4832 KB	Output is correct
17	Correct	57 ms	4876 KB	Output is correct
18	Correct	54 ms	4824 KB	Output is correct

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	3 ms	480 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	5 ms	544 KB	Output is correct
6	Correct	4 ms	468 KB	Output is correct
7	Correct	4 ms	476 KB	Output is correct
8	Correct	4 ms	480 KB	Output is correct
9	Correct	4 ms	476 KB	Output is correct
10	Correct	3 ms	476 KB	Output is correct
11	Correct	4 ms	480 KB	Output is correct
12	Correct	3 ms	484 KB	Output is correct
13	Correct	3 ms	536 KB	Output is correct
14	Correct	3 ms	448 KB	Output is correct
15	Correct	3 ms	436 KB	Output is correct
16	Correct	3 ms	440 KB	Output is correct
17	Correct	3 ms	468 KB	Output is correct
18	Correct	3 ms	472 KB	Output is correct
19	Correct	14 ms	1004 KB	Output is correct
20	Correct	15 ms	1084 KB	Output is correct
21	Correct	15 ms	1144 KB	Output is correct
22	Correct	17 ms	1116 KB	Output is correct
23	Correct	14 ms	1104 KB	Output is correct
24	Correct	15 ms	1052 KB	Output is correct
25	Correct	14 ms	1156 KB	Output is correct
26	Correct	15 ms	1092 KB	Output is correct
27	Correct	14 ms	1120 KB	Output is correct
28	Correct	13 ms	1088 KB	Output is correct
29	Correct	21 ms	1412 KB	Output is correct
30	Correct	70 ms	3040 KB	Output is correct
31	Correct	132 ms	4792 KB	Output is correct
32	Correct	138 ms	4828 KB	Output is correct
33	Correct	128 ms	4804 KB	Output is correct
34	Correct	130 ms	4812 KB	Output is correct
35	Correct	130 ms	4780 KB	Output is correct
36	Correct	145 ms	4832 KB	Output is correct
37	Correct	122 ms	4796 KB	Output is correct
38	Correct	80 ms	4896 KB	Output is correct
39	Correct	84 ms	4824 KB	Output is correct
40	Correct	83 ms	4824 KB	Output is correct
41	Correct	73 ms	4828 KB	Output is correct
42	Correct	82 ms	4792 KB	Output is correct
43	Correct	66 ms	4808 KB	Output is correct
44	Correct	53 ms	4832 KB	Output is correct
45	Correct	57 ms	4876 KB	Output is correct
46	Correct	54 ms	4824 KB	Output is correct
47	Correct	764 ms	15560 KB	Output is correct
48	Correct	4035 ms	48052 KB	Output is correct
49	Correct	5056 ms	52236 KB	Output is correct
50	Correct	4575 ms	52200 KB	Output is correct
51	Correct	4604 ms	52416 KB	Output is correct
52	Correct	4338 ms	52244 KB	Output is correct
53	Correct	4783 ms	52296 KB	Output is correct
54	Correct	3753 ms	52460 KB	Output is correct
55	Correct	4169 ms	52468 KB	Output is correct
56	Correct	3671 ms	52456 KB	Output is correct
57	Correct	4067 ms	52544 KB	Output is correct
58	Correct	3540 ms	52400 KB	Output is correct
59	Correct	3090 ms	51020 KB	Output is correct
60	Correct	3034 ms	51028 KB	Output is correct
61	Correct	3069 ms	51084 KB	Output is correct
62	Correct	2781 ms	51180 KB	Output is correct
63	Correct	2778 ms	51068 KB	Output is correct
64	Correct	2901 ms	50940 KB	Output is correct
65	Correct	2485 ms	50896 KB	Output is correct
66	Correct	2565 ms	50936 KB	Output is correct
67	Correct	2497 ms	50780 KB	Output is correct

Submission #711834

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