oj.uz

Submission #985184

# Submission time Handle Problem Language Result Execution time Memory
985184 2024-05-17T12:05:50 Z Kracken_180 Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 2097152 KB 
#include "sequence.h"
#include <vector>
#include <unordered_map>
#include <set>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int sequence(int N, vector<int> A) {
    vector<unordered_map<int, int>> prefixFreq(N + 1);
    for (int i = 0; i < N; ++i) {
        prefixFreq[i + 1] = prefixFreq[i];
        prefixFreq[i + 1][A[i]]++;
    }
 
    int maxOccurrences = 0;
    for (int l = 0; l < N; ++l) {
        multiset<int> leftSet, rightSet;
        unordered_map<int, int> freq;
        for (int r = l; r < N; ++r) {
            if (leftSet.empty() || A[r] <= *leftSet.rbegin()) {
                leftSet.insert(A[r]);
            } else {
                rightSet.insert(A[r]);
            }
 
            while (leftSet.size() > rightSet.size() + 1) {
                rightSet.insert(*leftSet.rbegin());
                leftSet.erase(prev(leftSet.end()));
            }
 
            while (rightSet.size() > leftSet.size()) {
                leftSet.insert(*rightSet.begin());
                rightSet.erase(rightSet.begin());
            }
 
            int median1 = *leftSet.rbegin();
            int median2 = (leftSet.size() + rightSet.size()) % 2 == 0 ? *rightSet.begin() : median1;
 
            freq[A[r]]++;
            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 2 ms 604 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 344 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 2 ms 604 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 523 ms 64500 KB Output is correct
14 Correct 514 ms 63984 KB Output is correct
15 Correct 266 ms 4228 KB Output is correct
16 Correct 259 ms 4188 KB Output is correct
17 Correct 255 ms 1160 KB Output is correct
18 Correct 463 ms 86100 KB Output is correct
19 Correct 504 ms 53520 KB Output is correct
20 Correct 481 ms 50736 KB Output is correct
21 Correct 494 ms 51796 KB Output is correct
22 Correct 504 ms 51660 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 Runtime error 1929 ms 2097152 KB Execution killed with signal 9
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 2019 ms 157520 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1879 ms 2097152 KB Execution killed with signal 9
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 2 ms 604 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 523 ms 64500 KB Output is correct
14 Correct 514 ms 63984 KB Output is correct
15 Correct 266 ms 4228 KB Output is correct
16 Correct 259 ms 4188 KB Output is correct
17 Correct 255 ms 1160 KB Output is correct
18 Correct 463 ms 86100 KB Output is correct
19 Correct 504 ms 53520 KB Output is correct
20 Correct 481 ms 50736 KB Output is correct
21 Correct 494 ms 51796 KB Output is correct
22 Correct 504 ms 51660 KB Output is correct
23 Runtime error 1796 ms 2097152 KB Execution killed with signal 9
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 2 ms 604 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 344 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 1 ms 500 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 523 ms 64500 KB Output is correct
14 Correct 514 ms 63984 KB Output is correct
15 Correct 266 ms 4228 KB Output is correct
16 Correct 259 ms 4188 KB Output is correct
17 Correct 255 ms 1160 KB Output is correct
18 Correct 463 ms 86100 KB Output is correct
19 Correct 504 ms 53520 KB Output is correct
20 Correct 481 ms 50736 KB Output is correct
21 Correct 494 ms 51796 KB Output is correct
22 Correct 504 ms 51660 KB Output is correct
23 Runtime error 1929 ms 2097152 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -