Submission #548097

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
548097	2022-04-12T11:55:39 Z	blue	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	6874 ms	365708 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())
 
struct sdata
{
	set<int> inds;
	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])
		{
			s[i].inds.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])
		{
			s[i].inds.erase(id);
			s[i].count--;
			s[i].currans = (s[i].inds.empty() ? -3'000'000 : *s[i].inds.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	3 ms	596 KB	Output is correct
2	Correct	3 ms	852 KB	Output is correct
3	Correct	9 ms	1748 KB	Output is correct
4	Correct	6 ms	1748 KB	Output is correct
5	Correct	6 ms	1748 KB	Output is correct
6	Correct	6 ms	1748 KB	Output is correct
7	Correct	6 ms	1748 KB	Output is correct
8	Correct	6 ms	1748 KB	Output is correct
9	Correct	7 ms	1720 KB	Output is correct
10	Correct	6 ms	1620 KB	Output is correct
11	Correct	7 ms	1716 KB	Output is correct
12	Correct	8 ms	1620 KB	Output is correct
13	Correct	6 ms	1620 KB	Output is correct
14	Correct	6 ms	1620 KB	Output is correct
15	Correct	7 ms	1620 KB	Output is correct
16	Correct	6 ms	1620 KB	Output is correct
17	Correct	6 ms	1620 KB	Output is correct
18	Correct	7 ms	1620 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	596 KB	Output is correct
2	Correct	3 ms	852 KB	Output is correct
3	Correct	9 ms	1748 KB	Output is correct
4	Correct	6 ms	1748 KB	Output is correct
5	Correct	6 ms	1748 KB	Output is correct
6	Correct	6 ms	1748 KB	Output is correct
7	Correct	6 ms	1748 KB	Output is correct
8	Correct	6 ms	1748 KB	Output is correct
9	Correct	7 ms	1720 KB	Output is correct
10	Correct	6 ms	1620 KB	Output is correct
11	Correct	7 ms	1716 KB	Output is correct
12	Correct	8 ms	1620 KB	Output is correct
13	Correct	6 ms	1620 KB	Output is correct
14	Correct	6 ms	1620 KB	Output is correct
15	Correct	7 ms	1620 KB	Output is correct
16	Correct	6 ms	1620 KB	Output is correct
17	Correct	6 ms	1620 KB	Output is correct
18	Correct	7 ms	1620 KB	Output is correct
19	Correct	27 ms	5460 KB	Output is correct
20	Correct	30 ms	6100 KB	Output is correct
21	Correct	30 ms	6116 KB	Output is correct
22	Correct	39 ms	6068 KB	Output is correct
23	Correct	42 ms	5944 KB	Output is correct
24	Correct	43 ms	5984 KB	Output is correct
25	Correct	33 ms	5892 KB	Output is correct
26	Correct	29 ms	5844 KB	Output is correct
27	Correct	26 ms	5816 KB	Output is correct
28	Correct	26 ms	5752 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	11304 KB	Output is correct
2	Correct	196 ms	23492 KB	Output is correct
3	Correct	374 ms	35888 KB	Output is correct
4	Correct	365 ms	35768 KB	Output is correct
5	Correct	344 ms	35712 KB	Output is correct
6	Correct	312 ms	35664 KB	Output is correct
7	Correct	331 ms	35552 KB	Output is correct
8	Correct	384 ms	35728 KB	Output is correct
9	Correct	330 ms	35544 KB	Output is correct
10	Correct	227 ms	32944 KB	Output is correct
11	Correct	201 ms	32932 KB	Output is correct
12	Correct	223 ms	32908 KB	Output is correct
13	Correct	179 ms	33052 KB	Output is correct
14	Correct	180 ms	32980 KB	Output is correct
15	Correct	185 ms	32932 KB	Output is correct
16	Correct	192 ms	32976 KB	Output is correct
17	Correct	179 ms	32968 KB	Output is correct
18	Correct	168 ms	32856 KB	Output is correct

Subtask #4
40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	596 KB	Output is correct
2	Correct	3 ms	852 KB	Output is correct
3	Correct	9 ms	1748 KB	Output is correct
4	Correct	6 ms	1748 KB	Output is correct
5	Correct	6 ms	1748 KB	Output is correct
6	Correct	6 ms	1748 KB	Output is correct
7	Correct	6 ms	1748 KB	Output is correct
8	Correct	6 ms	1748 KB	Output is correct
9	Correct	7 ms	1720 KB	Output is correct
10	Correct	6 ms	1620 KB	Output is correct
11	Correct	7 ms	1716 KB	Output is correct
12	Correct	8 ms	1620 KB	Output is correct
13	Correct	6 ms	1620 KB	Output is correct
14	Correct	6 ms	1620 KB	Output is correct
15	Correct	7 ms	1620 KB	Output is correct
16	Correct	6 ms	1620 KB	Output is correct
17	Correct	6 ms	1620 KB	Output is correct
18	Correct	7 ms	1620 KB	Output is correct
19	Correct	27 ms	5460 KB	Output is correct
20	Correct	30 ms	6100 KB	Output is correct
21	Correct	30 ms	6116 KB	Output is correct
22	Correct	39 ms	6068 KB	Output is correct
23	Correct	42 ms	5944 KB	Output is correct
24	Correct	43 ms	5984 KB	Output is correct
25	Correct	33 ms	5892 KB	Output is correct
26	Correct	29 ms	5844 KB	Output is correct
27	Correct	26 ms	5816 KB	Output is correct
28	Correct	26 ms	5752 KB	Output is correct
29	Correct	49 ms	11304 KB	Output is correct
30	Correct	196 ms	23492 KB	Output is correct
31	Correct	374 ms	35888 KB	Output is correct
32	Correct	365 ms	35768 KB	Output is correct
33	Correct	344 ms	35712 KB	Output is correct
34	Correct	312 ms	35664 KB	Output is correct
35	Correct	331 ms	35552 KB	Output is correct
36	Correct	384 ms	35728 KB	Output is correct
37	Correct	330 ms	35544 KB	Output is correct
38	Correct	227 ms	32944 KB	Output is correct
39	Correct	201 ms	32932 KB	Output is correct
40	Correct	223 ms	32908 KB	Output is correct
41	Correct	179 ms	33052 KB	Output is correct
42	Correct	180 ms	32980 KB	Output is correct
43	Correct	185 ms	32932 KB	Output is correct
44	Correct	192 ms	32976 KB	Output is correct
45	Correct	179 ms	32968 KB	Output is correct
46	Correct	168 ms	32856 KB	Output is correct
47	Correct	1490 ms	105724 KB	Output is correct
48	Correct	6213 ms	320516 KB	Output is correct
49	Correct	6874 ms	365432 KB	Output is correct
50	Correct	6668 ms	365424 KB	Output is correct
51	Correct	6349 ms	365464 KB	Output is correct
52	Correct	6039 ms	365528 KB	Output is correct
53	Correct	6059 ms	365424 KB	Output is correct
54	Correct	5381 ms	365652 KB	Output is correct
55	Correct	5884 ms	365652 KB	Output is correct
56	Correct	5444 ms	365640 KB	Output is correct
57	Correct	5853 ms	365708 KB	Output is correct
58	Correct	5418 ms	365540 KB	Output is correct
59	Correct	4528 ms	356512 KB	Output is correct
60	Correct	4666 ms	356508 KB	Output is correct
61	Correct	4621 ms	356492 KB	Output is correct
62	Correct	4347 ms	352364 KB	Output is correct
63	Correct	4358 ms	352416 KB	Output is correct
64	Correct	4317 ms	352380 KB	Output is correct
65	Correct	4057 ms	348380 KB	Output is correct
66	Correct	3944 ms	348316 KB	Output is correct
67	Correct	4003 ms	348448 KB	Output is correct

Submission #548097

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