Submission #760158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
760158	2023-06-17T08:45:30 Z	danikoynov	Sequence (APIO23_sequence)	C++17	28 / 100	2000 ms	29568 KB

sequence

#include "sequence.h"

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 10;
int occ[maxn];
int sequence(int N, vector<int> A)
{
    multiset < int > lf, rf;
    int ans = 1;
    for (int i = 0; i < N; i ++)
    {
        for (int j = 0; j <= N; j ++)
            occ[j] = 0;

        lf.clear();
        rf.clear();

        lf.insert(A[i]);
        occ[A[i]] ++;
        for (int j = i + 1; j < N; j ++)
        {
            occ[A[j]] ++;
            if (A[j] > *lf.rbegin())
                rf.insert(A[j]);
            else
                lf.insert(A[j]);

            while(lf.size() > rf.size() + 1)
            {
                int x = *lf.rbegin();
                lf.erase(lf.find(x));
                rf.insert(x);
            }
            while(rf.size() > lf.size())
            {
                int x = *rf.begin();
                rf.erase(rf.find(x));
                lf.insert(x);
            }

            if ((j - i + 1) % 2 == 0)
            {
                ans = max(ans, occ[*lf.rbegin()]);
                ans = max(ans, occ[*rf.begin()]);
            }
            else
            {
                ans = max(ans, occ[*lf.rbegin()]);
            }
        }
    }
    return ans;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct

Subtask #2

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	258 ms	400 KB	Output is correct
14	Correct	242 ms	404 KB	Output is correct
15	Correct	256 ms	404 KB	Output is correct
16	Correct	265 ms	400 KB	Output is correct
17	Correct	259 ms	404 KB	Output is correct
18	Correct	179 ms	396 KB	Output is correct
19	Correct	261 ms	396 KB	Output is correct
20	Correct	256 ms	400 KB	Output is correct
21	Correct	253 ms	400 KB	Output is correct
22	Correct	250 ms	400 KB	Output is correct

Subtask #3

0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Execution timed out	2063 ms	29568 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	212 KB	Output is correct
2	Execution timed out	2067 ms	29516 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	2078 ms	29564 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	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	258 ms	400 KB	Output is correct
14	Correct	242 ms	404 KB	Output is correct
15	Correct	256 ms	404 KB	Output is correct
16	Correct	265 ms	400 KB	Output is correct
17	Correct	259 ms	404 KB	Output is correct
18	Correct	179 ms	396 KB	Output is correct
19	Correct	261 ms	396 KB	Output is correct
20	Correct	256 ms	400 KB	Output is correct
21	Correct	253 ms	400 KB	Output is correct
22	Correct	250 ms	400 KB	Output is correct
23	Execution timed out	2059 ms	4936 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	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	312 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	258 ms	400 KB	Output is correct
14	Correct	242 ms	404 KB	Output is correct
15	Correct	256 ms	404 KB	Output is correct
16	Correct	265 ms	400 KB	Output is correct
17	Correct	259 ms	404 KB	Output is correct
18	Correct	179 ms	396 KB	Output is correct
19	Correct	261 ms	396 KB	Output is correct
20	Correct	256 ms	400 KB	Output is correct
21	Correct	253 ms	400 KB	Output is correct
22	Correct	250 ms	400 KB	Output is correct
23	Execution timed out	2063 ms	29568 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-