oj.uz

Submission #985205

# Submission time Handle Problem Language Result Execution time Memory
985205 2024-05-17T12:40:08 Z CrazyBotBoy Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 49112 KB 
#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <set>
#include <iostream>

using namespace std;

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

    // Iterate over each possible starting point of subarray
    for (int l = 0; l < N; ++l) {
        unordered_map<int, int> freq; // Frequency map for current subarray
        multiset<int> lower, upper;   // Two multisets to manage medians

        // Iterate over each possible ending point of subarray starting from 'l'
        for (int r = l; r < N; ++r) {
            int num = A[r];
            
            // Insert the number into one of the heaps
            if (lower.empty() || num <= *lower.rbegin()) {
                lower.insert(num);
            } else {
                upper.insert(num);
            }

            // Balance the heaps
            while (lower.size() > upper.size() + 1) {
                upper.insert(*lower.rbegin());
                lower.erase(prev(lower.end()));
            }
            while (upper.size() > lower.size()) {
                lower.insert(*upper.begin());
                upper.erase(upper.begin());
            }

            // Update frequency map
            freq[num]++;
            
            // Find the current medians
            int median1 = *lower.rbegin();
            int median2 = (lower.size() + upper.size()) % 2 == 0 ? *upper.begin() : median1;

            // Update maxOccurrences with frequency of the current medians
            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 1 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 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 418 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 257 ms 344 KB Output is correct
16 Correct 255 ms 520 KB Output is correct
17 Correct 256 ms 512 KB Output is correct
18 Correct 342 ms 864 KB Output is correct
19 Correct 414 ms 572 KB Output is correct
20 Correct 403 ms 576 KB Output is correct
21 Correct 423 ms 344 KB Output is correct
22 Correct 427 ms 568 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2021 ms 40376 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 2045 ms 27684 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 2029 ms 49112 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 418 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 257 ms 344 KB Output is correct
16 Correct 255 ms 520 KB Output is correct
17 Correct 256 ms 512 KB Output is correct
18 Correct 342 ms 864 KB Output is correct
19 Correct 414 ms 572 KB Output is correct
20 Correct 403 ms 576 KB Output is correct
21 Correct 423 ms 344 KB Output is correct
22 Correct 427 ms 568 KB Output is correct
23 Execution timed out 2051 ms 7368 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 418 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 257 ms 344 KB Output is correct
16 Correct 255 ms 520 KB Output is correct
17 Correct 256 ms 512 KB Output is correct
18 Correct 342 ms 864 KB Output is correct
19 Correct 414 ms 572 KB Output is correct
20 Correct 403 ms 576 KB Output is correct
21 Correct 423 ms 344 KB Output is correct
22 Correct 427 ms 568 KB Output is correct
23 Execution timed out 2021 ms 40376 KB Time limit exceeded
24 Halted 0 ms 0 KB -