oj.uz

Submission #982025

# Submission time Handle Problem Language Result Execution time Memory
982025 2024-05-13T18:08:47 Z vjudge1 Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 32128 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>;

struct MedianDS {
    multiset <ll, greater <ll> > st1; // big to small (mid...0)
    multiset <ll> st2; // small to big (mid...n)

    MedianDS () {}

    void stabilize () {
        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());
        }
    }

    void insert (ll x) {
        ll mid = (st2.size() ? *st2.begin() : 0);
        if (x >= mid) st2.insert(x);
        else st1.insert(x);
        stabilize();
    }

    void erase (ll x) {
        ll mid = (st2.size() ? *st2.begin() : 0);
        if (x >= mid) st2.erase(st2.find(x));
        else st1.erase(st1.find(x));
        stabilize();
    }

    pair <ll, ll> query () {
        if (st1.size() == st2.size()) { // two medians
            ll med1 = *st1.begin();
            ll med2 = *st2.begin();
            return { med1, med2 };
        } else { // one median
            assert(st2.size() > st1.size());
            ll med = *st2.begin();
            return { med, med };
        }
    }
};

int sequence (int n, vi ve) {
    for (int &i : ve) i--;
    ll ans = 0;
    for (ll l = 0; l < n; l++) {
        vll freq(n, 0);
        MedianDS ds;
        for (ll r = l; r < n; r++) {
            freq[ve[r]]++;
            ds.insert(ve[r]);
            auto [a, b] = ds.query();
            ans = max(ans, freq[a]);
            ans = max(ans, freq[b]);
        }
    }
    return int(ans);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 1 ms 344 KB Output is correct
9 Correct 2 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 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 1 ms 344 KB Output is correct
9 Correct 2 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 313 ms 540 KB Output is correct
14 Correct 313 ms 540 KB Output is correct
15 Correct 347 ms 348 KB Output is correct
16 Correct 353 ms 540 KB Output is correct
17 Correct 371 ms 536 KB Output is correct
18 Correct 285 ms 540 KB Output is correct
19 Correct 338 ms 540 KB Output is correct
20 Correct 347 ms 348 KB Output is correct
21 Correct 320 ms 548 KB Output is correct
22 Correct 316 ms 596 KB Output is correct

Subtask #3
0.0 / 7.0

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

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 2039 ms 31912 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 2058 ms 32056 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 1 ms 344 KB Output is correct
9 Correct 2 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 313 ms 540 KB Output is correct
14 Correct 313 ms 540 KB Output is correct
15 Correct 347 ms 348 KB Output is correct
16 Correct 353 ms 540 KB Output is correct
17 Correct 371 ms 536 KB Output is correct
18 Correct 285 ms 540 KB Output is correct
19 Correct 338 ms 540 KB Output is correct
20 Correct 347 ms 348 KB Output is correct
21 Correct 320 ms 548 KB Output is correct
22 Correct 316 ms 596 KB Output is correct
23 Execution timed out 2041 ms 5892 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 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 1 ms 344 KB Output is correct
9 Correct 2 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 313 ms 540 KB Output is correct
14 Correct 313 ms 540 KB Output is correct
15 Correct 347 ms 348 KB Output is correct
16 Correct 353 ms 540 KB Output is correct
17 Correct 371 ms 536 KB Output is correct
18 Correct 285 ms 540 KB Output is correct
19 Correct 338 ms 540 KB Output is correct
20 Correct 347 ms 348 KB Output is correct
21 Correct 320 ms 548 KB Output is correct
22 Correct 316 ms 596 KB Output is correct
23 Execution timed out 2062 ms 32128 KB Time limit exceeded
24 Halted 0 ms 0 KB -