oj.uz

Submission #981902

# Submission time Handle Problem Language Result Execution time Memory
981902 2024-05-13T16:13:55 Z vjudge1 Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 31856 KB 
#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;
using vi = vector <int>;
using ii = pair <ll, ll>;
using vii = vector <ii>;

int sequence (int n, vi ve) {
    for (int &i : ve) i--;
    ll ans = 0;
    for (ll l = 0; l < n; l++) {
        multiset <ll, greater <ll> > st1; // big to small (mid...0)
        multiset <ll> st2; // small to big (mid...n)
        vll freq(n, 0);
        for (ll r = l; r < n; r++) {
            ll mid = (st2.size() ? *st2.begin() : 0);
            freq[ve[r]]++;
            if (ve[r] >= mid) st2.insert(ve[r]);
            else st1.insert(ve[r]);
            while (st2.size() > st1.size()) {
                st1.insert(*st2.begin());
                st2.erase(st2.begin());
            }
            while (st1.size() > st2.size()) {
                st2.insert(*st1.begin());
                st1.erase(st1.begin());
            }
            if (st1.size() == st2.size()) { // two medians
                ll med1 = *st1.begin();
                ll med2 = *st2.begin();
                ans = max(ans, freq[med1]);
                ans = max(ans, freq[med2]);
            } else { // one median
                assert(st2.size() > st1.size());
                ll med = *st2.begin();
                ans = max(ans, freq[med]);
            }
        }
    }
    return int(ans);
}

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 600 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 1 ms 348 KB Output is correct
11 Correct 1 ms 436 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 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 600 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 1 ms 348 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 316 ms 348 KB Output is correct
14 Correct 321 ms 596 KB Output is correct
15 Correct 345 ms 344 KB Output is correct
16 Correct 346 ms 548 KB Output is correct
17 Correct 376 ms 536 KB Output is correct
18 Correct 282 ms 348 KB Output is correct
19 Correct 330 ms 344 KB Output is correct
20 Correct 345 ms 544 KB Output is correct
21 Correct 315 ms 544 KB Output is correct
22 Correct 318 ms 596 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 2071 ms 31568 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 2041 ms 31856 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 2024 ms 31600 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 600 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 1 ms 348 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 316 ms 348 KB Output is correct
14 Correct 321 ms 596 KB Output is correct
15 Correct 345 ms 344 KB Output is correct
16 Correct 346 ms 548 KB Output is correct
17 Correct 376 ms 536 KB Output is correct
18 Correct 282 ms 348 KB Output is correct
19 Correct 330 ms 344 KB Output is correct
20 Correct 345 ms 544 KB Output is correct
21 Correct 315 ms 544 KB Output is correct
22 Correct 318 ms 596 KB Output is correct
23 Execution timed out 2009 ms 5852 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 600 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 1 ms 348 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 316 ms 348 KB Output is correct
14 Correct 321 ms 596 KB Output is correct
15 Correct 345 ms 344 KB Output is correct
16 Correct 346 ms 548 KB Output is correct
17 Correct 376 ms 536 KB Output is correct
18 Correct 282 ms 348 KB Output is correct
19 Correct 330 ms 344 KB Output is correct
20 Correct 345 ms 544 KB Output is correct
21 Correct 315 ms 544 KB Output is correct
22 Correct 318 ms 596 KB Output is correct
23 Execution timed out 2071 ms 31568 KB Time limit exceeded
24 Halted 0 ms 0 KB -