#ifndef Nhoksocqt1
#include "sequence.h"
#endif // Nhoksocqt1
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 500005;
int val[MAXN], cnt[MAXN], nArr;
int sub2(void) {
int res(1);
for (int l = 1; l <= nArr; ++l) {
set<int> Set;
int pos(val[l]), cntPos(1);
Set.insert(pos);
++cnt[pos];
for (int r = l + 1; r <= nArr; ++r) {
cntPos += (val[r] <= pos);
if(++cnt[val[r]] == 1)
Set.insert(val[r]);
while(cntPos < (r - l + 1) / 2 + 1) {
auto it = Set.lower_bound(pos); ++it;
assert(it != Set.end());
pos = *it;
cntPos += cnt[pos];
}
while(cntPos - cnt[pos] >= (r - l + 1) / 2 + 1) {
cntPos -= cnt[pos];
auto it = Set.lower_bound(pos);
assert(it != Set.begin()); --it;
pos = *it;
}
//cout << l << ' ' << r << ' ' << pos << ' ' << cntPos << '\n';
res = max(res, cnt[pos]);
if((r - l + 1) % 2 == 0 && cntPos - cnt[pos] >= (r - l + 1) / 2) {
auto it = Set.lower_bound(pos);
assert(it != Set.begin()); --it;
res = max(res, cnt[*it]);
}
}
for (int r = l; r <= nArr; ++r)
--cnt[val[r]];
}
return res;
}
int sequence(int _N, vector<int> _A) {
nArr = _N;
for (int i = 1; i <= nArr; ++i)
val[i] = _A[i - 1];
if(nArr <= 2000)
return sub2();
}
#ifdef Nhoksocqt1
int main(void) {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define TASK "sequence"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
vector<int> _A;
int _N;
cin >> _N;
_A.resize(_N);
for (int i = 0; i < _N; ++i)
cin >> _A[i];
int ans = sequence(_N, _A);
cout << "ANSWER: " << ans << '\n';
return 0;
}
#endif // Nhoksocqt1
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:78:1: warning: control reaches end of non-void function [-Wreturn-type]
78 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
206 ms |
2572 KB |
Output is correct |
14 |
Correct |
201 ms |
2572 KB |
Output is correct |
15 |
Correct |
21 ms |
2392 KB |
Output is correct |
16 |
Correct |
22 ms |
2396 KB |
Output is correct |
17 |
Correct |
9 ms |
2516 KB |
Output is correct |
18 |
Correct |
192 ms |
2396 KB |
Output is correct |
19 |
Correct |
171 ms |
2652 KB |
Output is correct |
20 |
Correct |
152 ms |
2396 KB |
Output is correct |
21 |
Correct |
177 ms |
2396 KB |
Output is correct |
22 |
Correct |
183 ms |
2640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Execution timed out |
2062 ms |
26388 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
2 |
Execution timed out |
2009 ms |
9016 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
2031 ms |
34896 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
206 ms |
2572 KB |
Output is correct |
14 |
Correct |
201 ms |
2572 KB |
Output is correct |
15 |
Correct |
21 ms |
2392 KB |
Output is correct |
16 |
Correct |
22 ms |
2396 KB |
Output is correct |
17 |
Correct |
9 ms |
2516 KB |
Output is correct |
18 |
Correct |
192 ms |
2396 KB |
Output is correct |
19 |
Correct |
171 ms |
2652 KB |
Output is correct |
20 |
Correct |
152 ms |
2396 KB |
Output is correct |
21 |
Correct |
177 ms |
2396 KB |
Output is correct |
22 |
Correct |
183 ms |
2640 KB |
Output is correct |
23 |
Execution timed out |
2054 ms |
5960 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
0 ms |
2396 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
1 ms |
2392 KB |
Output is correct |
5 |
Correct |
1 ms |
2396 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
1 ms |
2396 KB |
Output is correct |
8 |
Correct |
1 ms |
2396 KB |
Output is correct |
9 |
Correct |
1 ms |
2396 KB |
Output is correct |
10 |
Correct |
1 ms |
2396 KB |
Output is correct |
11 |
Correct |
1 ms |
2492 KB |
Output is correct |
12 |
Correct |
1 ms |
2396 KB |
Output is correct |
13 |
Correct |
206 ms |
2572 KB |
Output is correct |
14 |
Correct |
201 ms |
2572 KB |
Output is correct |
15 |
Correct |
21 ms |
2392 KB |
Output is correct |
16 |
Correct |
22 ms |
2396 KB |
Output is correct |
17 |
Correct |
9 ms |
2516 KB |
Output is correct |
18 |
Correct |
192 ms |
2396 KB |
Output is correct |
19 |
Correct |
171 ms |
2652 KB |
Output is correct |
20 |
Correct |
152 ms |
2396 KB |
Output is correct |
21 |
Correct |
177 ms |
2396 KB |
Output is correct |
22 |
Correct |
183 ms |
2640 KB |
Output is correct |
23 |
Execution timed out |
2062 ms |
26388 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |