Submission #983361

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
983361	2024-05-15T11:05:55 Z	c2zi6	Sequence (APIO23_sequence)	C++17	28 / 100	848 ms	17492 KB

sequence

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "sequence.h"

namespace TEST2 {
	int n;
	VI a;
	int solve(VI A) {a = A, n = a.size();
		int ans = 0;
		replr(l, 0, n-1) {
			indset<PII> st;
			int UID = 0;
			replr(r, l, n-1) {
				st.insert({a[r], UID++});
				int med1 = st.find_by_order((st.size()-1)/2)->ff;
				int med2 = st.find_by_order(st.size()/2)->ff;
				setmax(ans, int(st.order_of_key(*st.upper_bound({med1, 2e9})) - st.order_of_key(*st.lower_bound({med1, -2e9}))));
				setmax(ans, int(st.order_of_key(*st.upper_bound({med2, 2e9})) - st.order_of_key(*st.lower_bound({med2, -2e9}))));
			}
		}
		return ans;
	}
};

namespace TEST3 {
	int n;
	VI a;
	int solve(VI A) {a = A, n = a.size();
		VI cnt, poqr, mec;
		cnt = poqr = mec = VI(n+2);
		for (int x : a) cnt[x]++;
		replr(i, 1, n) poqr[i] = poqr[i-1] + cnt[i-1];
		reprl(i, n, 1) mec[i] = mec[i+1] + cnt[i+1];
		
		int ans = 0;
		replr(i, 1, n) {
			int a = poqr[i], b = cnt[i], c = mec[i];
			if (a >= c - b) {
				setmax(ans, b);
				/* cout << "AY SIK KRNA EXNI MEDIAN " << i << endl; */
			}
		}
		return ans;
	}
};

int sequence(int n, VI a) {
	if (n <= 2e3) return TEST2::solve(a);
	return TEST3::solve(a);
	return 0;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 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	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct

Subtask #2
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 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	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	713 ms	344 KB	Output is correct
14	Correct	679 ms	560 KB	Output is correct
15	Correct	630 ms	564 KB	Output is correct
16	Correct	624 ms	564 KB	Output is correct
17	Correct	598 ms	348 KB	Output is correct
18	Correct	848 ms	560 KB	Output is correct
19	Correct	756 ms	564 KB	Output is correct
20	Correct	731 ms	596 KB	Output is correct
21	Correct	722 ms	560 KB	Output is correct
22	Correct	782 ms	568 KB	Output is correct

Subtask #3
0.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	42 ms	13904 KB	Output is correct
3	Correct	45 ms	17208 KB	Output is correct
4	Correct	38 ms	14928 KB	Output is correct
5	Correct	44 ms	17492 KB	Output is correct
6	Incorrect	44 ms	17232 KB	Output isn't correct
7	Halted	0 ms	0 KB	-

Subtask #4
0.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	37 ms	13908 KB	Output is correct
3	Incorrect	37 ms	13916 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	51 ms	13912 KB	Output is correct
2	Correct	49 ms	17452 KB	Output is correct
3	Incorrect	54 ms	17424 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6
0.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 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	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	713 ms	344 KB	Output is correct
14	Correct	679 ms	560 KB	Output is correct
15	Correct	630 ms	564 KB	Output is correct
16	Correct	624 ms	564 KB	Output is correct
17	Correct	598 ms	348 KB	Output is correct
18	Correct	848 ms	560 KB	Output is correct
19	Correct	756 ms	564 KB	Output is correct
20	Correct	731 ms	596 KB	Output is correct
21	Correct	722 ms	560 KB	Output is correct
22	Correct	782 ms	568 KB	Output is correct
23	Incorrect	7 ms	2652 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #7
0.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	2 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	2 ms	348 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	2 ms	348 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	713 ms	344 KB	Output is correct
14	Correct	679 ms	560 KB	Output is correct
15	Correct	630 ms	564 KB	Output is correct
16	Correct	624 ms	564 KB	Output is correct
17	Correct	598 ms	348 KB	Output is correct
18	Correct	848 ms	560 KB	Output is correct
19	Correct	756 ms	564 KB	Output is correct
20	Correct	731 ms	596 KB	Output is correct
21	Correct	722 ms	560 KB	Output is correct
22	Correct	782 ms	568 KB	Output is correct
23	Correct	42 ms	13904 KB	Output is correct
24	Correct	45 ms	17208 KB	Output is correct
25	Correct	38 ms	14928 KB	Output is correct
26	Correct	44 ms	17492 KB	Output is correct
27	Incorrect	44 ms	17232 KB	Output isn't correct
28	Halted	0 ms	0 KB	-

Submission #983361

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 17.0 / 17.0

Subtask #3 0.0 / 7.0

Subtask #4 0.0 / 12.0

Subtask #5 0.0 / 13.0

Subtask #6 0.0 / 22.0

Subtask #7 0.0 / 18.0

Subtask #1
11.0 / 11.0

Subtask #2
17.0 / 17.0

Subtask #3
0.0 / 7.0

Subtask #4
0.0 / 12.0

Subtask #5
0.0 / 13.0

Subtask #6
0.0 / 22.0

Subtask #7
0.0 / 18.0