oj.uz

Submission #985211

# Submission time Handle Problem Language Result Execution time Memory
985211 2024-05-17T12:48:30 Z CrazyBotBoy Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 49516 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 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 348 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 344 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 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 348 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 344 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 454 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 269 ms 516 KB Output is correct
16 Correct 254 ms 520 KB Output is correct
17 Correct 252 ms 344 KB Output is correct
18 Correct 349 ms 604 KB Output is correct
19 Correct 410 ms 348 KB Output is correct
20 Correct 453 ms 568 KB Output is correct
21 Correct 410 ms 564 KB Output is correct
22 Correct 408 ms 344 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 2069 ms 40540 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 2024 ms 27724 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 2050 ms 49516 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 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 348 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 344 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 454 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 269 ms 516 KB Output is correct
16 Correct 254 ms 520 KB Output is correct
17 Correct 252 ms 344 KB Output is correct
18 Correct 349 ms 604 KB Output is correct
19 Correct 410 ms 348 KB Output is correct
20 Correct 453 ms 568 KB Output is correct
21 Correct 410 ms 564 KB Output is correct
22 Correct 408 ms 344 KB Output is correct
23 Execution timed out 2009 ms 7232 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 344 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 500 KB Output is correct
6 Correct 1 ms 348 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 344 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 454 ms 604 KB Output is correct
14 Correct 421 ms 604 KB Output is correct
15 Correct 269 ms 516 KB Output is correct
16 Correct 254 ms 520 KB Output is correct
17 Correct 252 ms 344 KB Output is correct
18 Correct 349 ms 604 KB Output is correct
19 Correct 410 ms 348 KB Output is correct
20 Correct 453 ms 568 KB Output is correct
21 Correct 410 ms 564 KB Output is correct
22 Correct 408 ms 344 KB Output is correct
23 Execution timed out 2069 ms 40540 KB Time limit exceeded
24 Halted 0 ms 0 KB -