Submission #985189

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
985189	2024-05-17T12:09:23 Z	CrazyBotBoy	Sequence (APIO23_sequence)	C++17	28 / 100	2000 ms	49128 KB

sequence

#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <set>
#include <iostream>
#include <algorithm>

using namespace std;

int sequence(int N, vector<int> A) {
    int maxOccurrences = 0;

    for (int l = 0; l < N; ++l) {
        unordered_map<int, int> freq;
        multiset<int> minHeap, maxHeap;

        for (int r = l; r < N; ++r) {
            int num = A[r];
            if (maxHeap.empty() || num <= *maxHeap.rbegin()) {
                maxHeap.insert(num);
            } else {
                minHeap.insert(num);
            }

            if (maxHeap.size() > minHeap.size() + 1) {
                minHeap.insert(*maxHeap.rbegin());
                maxHeap.erase(--maxHeap.end());
            } else if (minHeap.size() > maxHeap.size()) {
                maxHeap.insert(*minHeap.begin());
                minHeap.erase(minHeap.begin());
            }

            freq[num]++;

            int median1 = *maxHeap.rbegin();
            int median2 = (maxHeap.size() + minHeap.size()) % 2 == 0 ? *minHeap.begin() : median1;

            maxOccurrences = max(maxOccurrences, freq[median1]);
            if (median1 != median2) {
                maxOccurrences = max(maxOccurrences, freq[median2]);
            }
        }
    }

    return maxOccurrences;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	440 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	440 KB	Output is correct
13	Correct	421 ms	604 KB	Output is correct
14	Correct	421 ms	600 KB	Output is correct
15	Correct	253 ms	344 KB	Output is correct
16	Correct	249 ms	348 KB	Output is correct
17	Correct	248 ms	344 KB	Output is correct
18	Correct	338 ms	600 KB	Output is correct
19	Correct	415 ms	348 KB	Output is correct
20	Correct	401 ms	572 KB	Output is correct
21	Correct	414 ms	572 KB	Output is correct
22	Correct	428 ms	348 KB	Output is correct

Subtask #3

0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Execution timed out	2052 ms	40384 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Execution timed out	2029 ms	28008 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2032 ms	49128 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6

0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	440 KB	Output is correct
13	Correct	421 ms	604 KB	Output is correct
14	Correct	421 ms	600 KB	Output is correct
15	Correct	253 ms	344 KB	Output is correct
16	Correct	249 ms	348 KB	Output is correct
17	Correct	248 ms	344 KB	Output is correct
18	Correct	338 ms	600 KB	Output is correct
19	Correct	415 ms	348 KB	Output is correct
20	Correct	401 ms	572 KB	Output is correct
21	Correct	414 ms	572 KB	Output is correct
22	Correct	428 ms	348 KB	Output is correct
23	Execution timed out	2060 ms	7176 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #7

0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	436 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	444 KB	Output is correct
12	Correct	1 ms	440 KB	Output is correct
13	Correct	421 ms	604 KB	Output is correct
14	Correct	421 ms	600 KB	Output is correct
15	Correct	253 ms	344 KB	Output is correct
16	Correct	249 ms	348 KB	Output is correct
17	Correct	248 ms	344 KB	Output is correct
18	Correct	338 ms	600 KB	Output is correct
19	Correct	415 ms	348 KB	Output is correct
20	Correct	401 ms	572 KB	Output is correct
21	Correct	414 ms	572 KB	Output is correct
22	Correct	428 ms	348 KB	Output is correct
23	Execution timed out	2052 ms	40384 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-