Submission #548098

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548098	2022-04-12T11:58:13 Z	blue	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	4034 ms	212352 KB

bubblesort2

#include "bubblesort2.h"
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
 
using vi = vector<int>;
using pii = pair<int, int>;
#define sz(x) int(x.size())

set<int> inds[1'000'000];
 
struct sdata
{
	int currans;
	int count;
};
 
sdata combine(sdata X, sdata Y)
{
	sdata res;
	res.count = X.count + Y.count;
	res.currans = max(X.currans, Y.currans - X.count);
	return res;
}
 
int N, Q;
vi A;
 
struct segtree
{
	int Z;
	vi l, r;
	vector<sdata> s;
 
	void build(int i, int L, int R)
	{
		l[i] = L;
		r[i] = R;
		if(L == R)
		{
			s[i].currans = -3'000'000;
			s[i].count = 0;
		}
		else
		{
			int m = (L+R)/2;
			build(2*i, L, m);
			build(2*i+1, m+1, R);
			s[i] = combine(s[2*i], s[2*i+1]);
		}
 
		// cerr << L << ' ' << R << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
 
	segtree(int K)
	{
		Z = 4*K;
 
		l = r = vi(1+Z);
		s = vector<sdata>(1+Z);
 
		build(1, 0, K-1);
	}
 
	void insert(int i, int p, int id)
	{
		if(l[i] == r[i])
		{
			inds[l[i]].insert(id);
			s[i].currans = max(s[i].currans, id);
			s[i].count++;
		}
		else
		{
			if(p <= (l[i]+r[i])/2)
				insert(2*i, p, id);
			else
				insert(2*i+1, p, id);
 
			s[i] = combine(s[2*i], s[2*i+1]);
		}
 
		// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
 
	void erase(int i, int p, int id)
	{
		if(l[i] == r[i])
		{
			inds[l[i]].erase(id);
			s[i].count--;
			s[i].currans = (inds[l[i]].empty() ? -3'000'000 : *inds[l[i]].rbegin());
		}
		else
		{
			if(p <= (l[i]+r[i])/2)
				erase(2*i, p, id);
			else
				erase(2*i+1, p, id);
 
			s[i] = combine(s[2*i], s[2*i+1]);
		}

		// cerr << l[i] << ' ' << r[i] << " : " << s[i].currans << ' ' << s[i].count << '\n';
	}
};
 
vi countScans(vi A_, vi X, vi V)
{
	A = A_;
	N = sz(A);
	Q = sz(X);
 
	map<pii, int> vals;
	for(int i = 0; i < N; i++)
		vals[{A[i], i}] = 0;
 
	for(int j = 0; j < Q; j++)
		vals[{V[j], X[j]}] = 0;
 
	int ct = -1;
	for(auto& z : vals)
	{
		z.second = ++ct;

		// cerr << z.first.first << " - " << z.second << '\n';
	}
 
	// cerr << "values # = " << sz(vals) << '\n';
 
	vi answer(Q);


 
 
	segtree S(N+Q);
 
	for(int i = 0; i < N; i++)
	{
		S.insert(1, vals[{A[i], i}], i);
	}
 
	for(int j = 0; j < Q; j++)
	{
		S.erase(1, vals[{A[X[j]], X[j]}], X[j]);
		A[X[j]] = V[j];
		S.insert(1, vals[{A[X[j]], X[j]}], X[j]);
 
		answer[j] = S.s[1].currans;
	}
 
	return answer;
}

Subtask #1
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47404 KB	Output is correct
2	Correct	24 ms	47472 KB	Output is correct
3	Correct	26 ms	47920 KB	Output is correct
4	Correct	26 ms	47940 KB	Output is correct
5	Correct	28 ms	47848 KB	Output is correct
6	Correct	28 ms	47904 KB	Output is correct
7	Correct	26 ms	47956 KB	Output is correct
8	Correct	26 ms	47956 KB	Output is correct
9	Correct	26 ms	47932 KB	Output is correct
10	Correct	26 ms	47888 KB	Output is correct
11	Correct	25 ms	47812 KB	Output is correct
12	Correct	27 ms	47912 KB	Output is correct
13	Correct	26 ms	47852 KB	Output is correct
14	Correct	26 ms	47828 KB	Output is correct
15	Correct	25 ms	47904 KB	Output is correct
16	Correct	25 ms	47844 KB	Output is correct
17	Correct	25 ms	47828 KB	Output is correct
18	Correct	26 ms	47812 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47404 KB	Output is correct
2	Correct	24 ms	47472 KB	Output is correct
3	Correct	26 ms	47920 KB	Output is correct
4	Correct	26 ms	47940 KB	Output is correct
5	Correct	28 ms	47848 KB	Output is correct
6	Correct	28 ms	47904 KB	Output is correct
7	Correct	26 ms	47956 KB	Output is correct
8	Correct	26 ms	47956 KB	Output is correct
9	Correct	26 ms	47932 KB	Output is correct
10	Correct	26 ms	47888 KB	Output is correct
11	Correct	25 ms	47812 KB	Output is correct
12	Correct	27 ms	47912 KB	Output is correct
13	Correct	26 ms	47852 KB	Output is correct
14	Correct	26 ms	47828 KB	Output is correct
15	Correct	25 ms	47904 KB	Output is correct
16	Correct	25 ms	47844 KB	Output is correct
17	Correct	25 ms	47828 KB	Output is correct
18	Correct	26 ms	47812 KB	Output is correct
19	Correct	39 ms	49740 KB	Output is correct
20	Correct	40 ms	49956 KB	Output is correct
21	Correct	39 ms	49968 KB	Output is correct
22	Correct	41 ms	50004 KB	Output is correct
23	Correct	40 ms	49840 KB	Output is correct
24	Correct	38 ms	49840 KB	Output is correct
25	Correct	38 ms	49832 KB	Output is correct
26	Correct	38 ms	49876 KB	Output is correct
27	Correct	40 ms	49712 KB	Output is correct
28	Correct	38 ms	49744 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	52592 KB	Output is correct
2	Correct	118 ms	58428 KB	Output is correct
3	Correct	215 ms	64228 KB	Output is correct
4	Correct	229 ms	64224 KB	Output is correct
5	Correct	208 ms	64176 KB	Output is correct
6	Correct	209 ms	64108 KB	Output is correct
7	Correct	209 ms	63944 KB	Output is correct
8	Correct	207 ms	64076 KB	Output is correct
9	Correct	200 ms	64112 KB	Output is correct
10	Correct	132 ms	61516 KB	Output is correct
11	Correct	130 ms	61492 KB	Output is correct
12	Correct	126 ms	61488 KB	Output is correct
13	Correct	125 ms	61500 KB	Output is correct
14	Correct	149 ms	61516 KB	Output is correct
15	Correct	117 ms	61440 KB	Output is correct
16	Correct	108 ms	61428 KB	Output is correct
17	Correct	102 ms	61488 KB	Output is correct
18	Correct	102 ms	61464 KB	Output is correct

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	47404 KB	Output is correct
2	Correct	24 ms	47472 KB	Output is correct
3	Correct	26 ms	47920 KB	Output is correct
4	Correct	26 ms	47940 KB	Output is correct
5	Correct	28 ms	47848 KB	Output is correct
6	Correct	28 ms	47904 KB	Output is correct
7	Correct	26 ms	47956 KB	Output is correct
8	Correct	26 ms	47956 KB	Output is correct
9	Correct	26 ms	47932 KB	Output is correct
10	Correct	26 ms	47888 KB	Output is correct
11	Correct	25 ms	47812 KB	Output is correct
12	Correct	27 ms	47912 KB	Output is correct
13	Correct	26 ms	47852 KB	Output is correct
14	Correct	26 ms	47828 KB	Output is correct
15	Correct	25 ms	47904 KB	Output is correct
16	Correct	25 ms	47844 KB	Output is correct
17	Correct	25 ms	47828 KB	Output is correct
18	Correct	26 ms	47812 KB	Output is correct
19	Correct	39 ms	49740 KB	Output is correct
20	Correct	40 ms	49956 KB	Output is correct
21	Correct	39 ms	49968 KB	Output is correct
22	Correct	41 ms	50004 KB	Output is correct
23	Correct	40 ms	49840 KB	Output is correct
24	Correct	38 ms	49840 KB	Output is correct
25	Correct	38 ms	49832 KB	Output is correct
26	Correct	38 ms	49876 KB	Output is correct
27	Correct	40 ms	49712 KB	Output is correct
28	Correct	38 ms	49744 KB	Output is correct
29	Correct	50 ms	52592 KB	Output is correct
30	Correct	118 ms	58428 KB	Output is correct
31	Correct	215 ms	64228 KB	Output is correct
32	Correct	229 ms	64224 KB	Output is correct
33	Correct	208 ms	64176 KB	Output is correct
34	Correct	209 ms	64108 KB	Output is correct
35	Correct	209 ms	63944 KB	Output is correct
36	Correct	207 ms	64076 KB	Output is correct
37	Correct	200 ms	64112 KB	Output is correct
38	Correct	132 ms	61516 KB	Output is correct
39	Correct	130 ms	61492 KB	Output is correct
40	Correct	126 ms	61488 KB	Output is correct
41	Correct	125 ms	61500 KB	Output is correct
42	Correct	149 ms	61516 KB	Output is correct
43	Correct	117 ms	61440 KB	Output is correct
44	Correct	108 ms	61428 KB	Output is correct
45	Correct	102 ms	61488 KB	Output is correct
46	Correct	102 ms	61464 KB	Output is correct
47	Correct	945 ms	97616 KB	Output is correct
48	Correct	3702 ms	196808 KB	Output is correct
49	Correct	4032 ms	212232 KB	Output is correct
50	Correct	4009 ms	212204 KB	Output is correct
51	Correct	3963 ms	212172 KB	Output is correct
52	Correct	4034 ms	212100 KB	Output is correct
53	Correct	3982 ms	212232 KB	Output is correct
54	Correct	3541 ms	212284 KB	Output is correct
55	Correct	3916 ms	212176 KB	Output is correct
56	Correct	3551 ms	212292 KB	Output is correct
57	Correct	3781 ms	212212 KB	Output is correct
58	Correct	3488 ms	212352 KB	Output is correct
59	Correct	2982 ms	204504 KB	Output is correct
60	Correct	3047 ms	204512 KB	Output is correct
61	Correct	3087 ms	204212 KB	Output is correct
62	Correct	2845 ms	200308 KB	Output is correct
63	Correct	2836 ms	200392 KB	Output is correct
64	Correct	2765 ms	200268 KB	Output is correct
65	Correct	2603 ms	196100 KB	Output is correct
66	Correct	2594 ms	196172 KB	Output is correct
67	Correct	2689 ms	195984 KB	Output is correct

Submission #548098

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