Submission #957095

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
957095	2024-04-03T00:22:45 Z	MuntherCarrot	Bubble Sort 2 (JOI18_bubblesort2)	C++14	60 / 100	3702 ms	12116 KB

bubblesort2

// by me
#include "bubblesort2.h"
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define all(x) x.begin(), x.end()
 
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V){
	int Q = X.size();
	int N = A.size();
	vector<int> ans(Q, 0);
	if(N <= 8000){
		for(int i = 0; i < Q; i++){
			A[X[i]] = V[i];
			vector<int> f(N);
			iota(all(f), 0);
			sort(all(f), [&](int a, int b){
				return A[a] < A[b];
			});
			for(int j = 0; j < N; j++){
				ans[i] = max(ans[i], f[j] - j);
			}
		}
		return ans;
	}
	vector<set<int>> f(101);
	for(int i = 0; i < N; i++){
		f[A[i]].insert(i);
	}
	for(int i = 0; i < Q; i++){
		f[A[X[i]]].erase(X[i]);
		A[X[i]] = V[i];
		f[A[X[i]]].insert(X[i]);
		int x = 0;
		for(auto &st : f){
			if(st.empty()) continue;
			x += st.size();
          	int mx = *prev(st.end());
			ans[i] = max(ans[i], mx - x + 1);
		}
	}
	return ans;
}
 
//
/*
int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}
 
int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
 
	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
 
	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
 
	std::vector<int> res=countScans(A,X,V);
 
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}
//*/
// by me

Subtask #1
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	600 KB	Output is correct
2	Correct	30 ms	348 KB	Output is correct
3	Correct	199 ms	344 KB	Output is correct
4	Correct	195 ms	520 KB	Output is correct
5	Correct	185 ms	520 KB	Output is correct
6	Correct	116 ms	520 KB	Output is correct
7	Correct	154 ms	520 KB	Output is correct
8	Correct	175 ms	772 KB	Output is correct
9	Correct	195 ms	520 KB	Output is correct
10	Correct	106 ms	492 KB	Output is correct
11	Correct	101 ms	516 KB	Output is correct
12	Correct	110 ms	348 KB	Output is correct
13	Correct	106 ms	348 KB	Output is correct
14	Correct	101 ms	344 KB	Output is correct
15	Correct	102 ms	508 KB	Output is correct
16	Correct	88 ms	508 KB	Output is correct
17	Correct	89 ms	348 KB	Output is correct
18	Correct	79 ms	348 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	600 KB	Output is correct
2	Correct	30 ms	348 KB	Output is correct
3	Correct	199 ms	344 KB	Output is correct
4	Correct	195 ms	520 KB	Output is correct
5	Correct	185 ms	520 KB	Output is correct
6	Correct	116 ms	520 KB	Output is correct
7	Correct	154 ms	520 KB	Output is correct
8	Correct	175 ms	772 KB	Output is correct
9	Correct	195 ms	520 KB	Output is correct
10	Correct	106 ms	492 KB	Output is correct
11	Correct	101 ms	516 KB	Output is correct
12	Correct	110 ms	348 KB	Output is correct
13	Correct	106 ms	348 KB	Output is correct
14	Correct	101 ms	344 KB	Output is correct
15	Correct	102 ms	508 KB	Output is correct
16	Correct	88 ms	508 KB	Output is correct
17	Correct	89 ms	348 KB	Output is correct
18	Correct	79 ms	348 KB	Output is correct
19	Correct	2847 ms	796 KB	Output is correct
20	Correct	3702 ms	856 KB	Output is correct
21	Correct	3231 ms	860 KB	Output is correct
22	Correct	3647 ms	860 KB	Output is correct
23	Correct	2077 ms	824 KB	Output is correct
24	Correct	2089 ms	824 KB	Output is correct
25	Correct	2061 ms	820 KB	Output is correct
26	Correct	2117 ms	820 KB	Output is correct
27	Correct	2052 ms	812 KB	Output is correct
28	Correct	2051 ms	824 KB	Output is correct

Subtask #3
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	1884 KB	Output is correct
2	Correct	34 ms	3384 KB	Output is correct
3	Correct	54 ms	4700 KB	Output is correct
4	Correct	53 ms	4700 KB	Output is correct
5	Correct	53 ms	4700 KB	Output is correct
6	Correct	52 ms	4728 KB	Output is correct
7	Correct	52 ms	4700 KB	Output is correct
8	Correct	52 ms	4700 KB	Output is correct
9	Correct	52 ms	4696 KB	Output is correct
10	Correct	46 ms	4700 KB	Output is correct
11	Correct	45 ms	4804 KB	Output is correct
12	Correct	52 ms	4700 KB	Output is correct
13	Correct	43 ms	4700 KB	Output is correct
14	Correct	44 ms	4700 KB	Output is correct
15	Correct	42 ms	4696 KB	Output is correct
16	Correct	43 ms	4588 KB	Output is correct
17	Correct	39 ms	4700 KB	Output is correct
18	Correct	43 ms	4700 KB	Output is correct

Subtask #4
0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	600 KB	Output is correct
2	Correct	30 ms	348 KB	Output is correct
3	Correct	199 ms	344 KB	Output is correct
4	Correct	195 ms	520 KB	Output is correct
5	Correct	185 ms	520 KB	Output is correct
6	Correct	116 ms	520 KB	Output is correct
7	Correct	154 ms	520 KB	Output is correct
8	Correct	175 ms	772 KB	Output is correct
9	Correct	195 ms	520 KB	Output is correct
10	Correct	106 ms	492 KB	Output is correct
11	Correct	101 ms	516 KB	Output is correct
12	Correct	110 ms	348 KB	Output is correct
13	Correct	106 ms	348 KB	Output is correct
14	Correct	101 ms	344 KB	Output is correct
15	Correct	102 ms	508 KB	Output is correct
16	Correct	88 ms	508 KB	Output is correct
17	Correct	89 ms	348 KB	Output is correct
18	Correct	79 ms	348 KB	Output is correct
19	Correct	2847 ms	796 KB	Output is correct
20	Correct	3702 ms	856 KB	Output is correct
21	Correct	3231 ms	860 KB	Output is correct
22	Correct	3647 ms	860 KB	Output is correct
23	Correct	2077 ms	824 KB	Output is correct
24	Correct	2089 ms	824 KB	Output is correct
25	Correct	2061 ms	820 KB	Output is correct
26	Correct	2117 ms	820 KB	Output is correct
27	Correct	2052 ms	812 KB	Output is correct
28	Correct	2051 ms	824 KB	Output is correct
29	Correct	7 ms	1884 KB	Output is correct
30	Correct	34 ms	3384 KB	Output is correct
31	Correct	54 ms	4700 KB	Output is correct
32	Correct	53 ms	4700 KB	Output is correct
33	Correct	53 ms	4700 KB	Output is correct
34	Correct	52 ms	4728 KB	Output is correct
35	Correct	52 ms	4700 KB	Output is correct
36	Correct	52 ms	4700 KB	Output is correct
37	Correct	52 ms	4696 KB	Output is correct
38	Correct	46 ms	4700 KB	Output is correct
39	Correct	45 ms	4804 KB	Output is correct
40	Correct	52 ms	4700 KB	Output is correct
41	Correct	43 ms	4700 KB	Output is correct
42	Correct	44 ms	4700 KB	Output is correct
43	Correct	42 ms	4696 KB	Output is correct
44	Correct	43 ms	4588 KB	Output is correct
45	Correct	39 ms	4700 KB	Output is correct
46	Correct	43 ms	4700 KB	Output is correct
47	Runtime error	39 ms	12116 KB	Execution killed with signal 11
48	Halted	0 ms	0 KB	-

Submission #957095

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 22.0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
22.0 / 22.0

Subtask #4
0 / 40.0