Submission #547633

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
547633	2022-04-11T06:32:08 Z	cig32	Bubble Sort 2 (JOI18_bubblesort2)	C++17	17 / 100	9000 ms	5800 KB

bubblesort2

#include "bubblesort2.h"

#include <cstdio>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <queue>
#include <algorithm>

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
  int N=A.size();
	int Q=X.size();
	std::vector<int> answer(Q);
	for (int j=0;j<Q;j++) {
		A[X[j]] = V[j];
    
    int B[N];
    for(int i=0; i<N; i++) B[i] = A[i];
    std::sort(B, B+N);
    int P[N];
    std::unordered_map<int, std::queue<int> >mp;
    for(int i=0; i<N; i++) mp[B[i]].push(i);
    answer[j] = 0;
    for(int i=0; i<N; i++) {
      P[i] = mp[A[i]].front();
      mp[A[i]].pop();
      answer[j] = std::max(answer[j], i - P[i]);
    }
	}
	return answer;
}

Subtask #1

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	724 KB	Output is correct
2	Correct	222 ms	852 KB	Output is correct
3	Correct	1307 ms	1832 KB	Output is correct
4	Correct	1302 ms	1828 KB	Output is correct
5	Correct	1276 ms	1928 KB	Output is correct
6	Correct	1293 ms	1956 KB	Output is correct
7	Correct	1260 ms	1828 KB	Output is correct
8	Correct	1253 ms	1828 KB	Output is correct
9	Correct	1267 ms	1832 KB	Output is correct
10	Correct	1078 ms	1940 KB	Output is correct
11	Correct	1055 ms	1820 KB	Output is correct
12	Correct	1040 ms	1828 KB	Output is correct
13	Correct	1057 ms	1820 KB	Output is correct
14	Correct	1048 ms	1828 KB	Output is correct
15	Correct	1049 ms	1824 KB	Output is correct
16	Correct	1008 ms	1820 KB	Output is correct
17	Correct	1014 ms	1868 KB	Output is correct
18	Correct	1056 ms	1992 KB	Output is correct

Subtask #2

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	724 KB	Output is correct
2	Correct	222 ms	852 KB	Output is correct
3	Correct	1307 ms	1832 KB	Output is correct
4	Correct	1302 ms	1828 KB	Output is correct
5	Correct	1276 ms	1928 KB	Output is correct
6	Correct	1293 ms	1956 KB	Output is correct
7	Correct	1260 ms	1828 KB	Output is correct
8	Correct	1253 ms	1828 KB	Output is correct
9	Correct	1267 ms	1832 KB	Output is correct
10	Correct	1078 ms	1940 KB	Output is correct
11	Correct	1055 ms	1820 KB	Output is correct
12	Correct	1040 ms	1828 KB	Output is correct
13	Correct	1057 ms	1820 KB	Output is correct
14	Correct	1048 ms	1828 KB	Output is correct
15	Correct	1049 ms	1824 KB	Output is correct
16	Correct	1008 ms	1820 KB	Output is correct
17	Correct	1014 ms	1868 KB	Output is correct
18	Correct	1056 ms	1992 KB	Output is correct
19	Execution timed out	9086 ms	5800 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

Subtask #3

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4155 ms	996 KB	Output is correct
2	Execution timed out	9027 ms	1968 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	724 KB	Output is correct
2	Correct	222 ms	852 KB	Output is correct
3	Correct	1307 ms	1832 KB	Output is correct
4	Correct	1302 ms	1828 KB	Output is correct
5	Correct	1276 ms	1928 KB	Output is correct
6	Correct	1293 ms	1956 KB	Output is correct
7	Correct	1260 ms	1828 KB	Output is correct
8	Correct	1253 ms	1828 KB	Output is correct
9	Correct	1267 ms	1832 KB	Output is correct
10	Correct	1078 ms	1940 KB	Output is correct
11	Correct	1055 ms	1820 KB	Output is correct
12	Correct	1040 ms	1828 KB	Output is correct
13	Correct	1057 ms	1820 KB	Output is correct
14	Correct	1048 ms	1828 KB	Output is correct
15	Correct	1049 ms	1824 KB	Output is correct
16	Correct	1008 ms	1820 KB	Output is correct
17	Correct	1014 ms	1868 KB	Output is correct
18	Correct	1056 ms	1992 KB	Output is correct
19	Execution timed out	9086 ms	5800 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-