#include "sequence.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define ptr(A) shared_ptr<A>
using namespace std;
const int MAX_N = 1e5;
struct BIT {
vector<int> bit = vector<int> (MAX_N, 0);
void update(int i, int d) {
for ( ; i < bit.size(); i |= i + 1)
bit[i] += d;
}
int sum(int i) {
int ans = 0;
for ( ; i >= 0; i = (i & (i + 1)) - 1)
ans += bit[i];
return ans;
}
int sum (int l, int r) {
return sum(r) - (l ? sum(l - 1) : 0);
}
};
int query(int i, BIT& ft, bool even) {
int l = 1, r = MAX_N, m;
while (l < r) {
m = (l+r)/2;
if (ft.sum(m) >= i)
r = m;
else l = m+1;
}
int ans = ft.sum(l, l);
if (even && i == ft.sum(l))
ans = max(ans, ft.sum(l+1, l+1));
// cout << l << ' ' << ans << '\n';
return ans;
}
int sequence(int N, vector<int> A) {
int maxi = 0;
for (int l = 0; l < N; l++) {
BIT ft;
for (int r = l; r < N; r++) {
// cout << "** " << l << ' ' << r << '\n';
ft.update(A[r], 1);
int sz = r-l+1;
int a = sz/2 + (sz & 1);
maxi = max(maxi, query(a, ft, !(sz & 1)));
}
}
return maxi;
}
Compilation message
sequence.cpp: In member function 'void BIT::update(int, int)':
sequence.cpp:24:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | for ( ; i < bit.size(); i |= i + 1)
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
248 ms |
860 KB |
Output is correct |
14 |
Correct |
271 ms |
856 KB |
Output is correct |
15 |
Correct |
188 ms |
820 KB |
Output is correct |
16 |
Correct |
181 ms |
856 KB |
Output is correct |
17 |
Correct |
165 ms |
724 KB |
Output is correct |
18 |
Correct |
270 ms |
980 KB |
Output is correct |
19 |
Correct |
249 ms |
860 KB |
Output is correct |
20 |
Correct |
208 ms |
860 KB |
Output is correct |
21 |
Incorrect |
254 ms |
860 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Execution timed out |
2058 ms |
4732 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Execution timed out |
2088 ms |
4952 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2013 ms |
4732 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
248 ms |
860 KB |
Output is correct |
14 |
Correct |
271 ms |
856 KB |
Output is correct |
15 |
Correct |
188 ms |
820 KB |
Output is correct |
16 |
Correct |
181 ms |
856 KB |
Output is correct |
17 |
Correct |
165 ms |
724 KB |
Output is correct |
18 |
Correct |
270 ms |
980 KB |
Output is correct |
19 |
Correct |
249 ms |
860 KB |
Output is correct |
20 |
Correct |
208 ms |
860 KB |
Output is correct |
21 |
Incorrect |
254 ms |
860 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
724 KB |
Output is correct |
2 |
Correct |
1 ms |
724 KB |
Output is correct |
3 |
Correct |
1 ms |
724 KB |
Output is correct |
4 |
Correct |
1 ms |
724 KB |
Output is correct |
5 |
Correct |
2 ms |
724 KB |
Output is correct |
6 |
Correct |
1 ms |
724 KB |
Output is correct |
7 |
Correct |
1 ms |
724 KB |
Output is correct |
8 |
Correct |
2 ms |
724 KB |
Output is correct |
9 |
Correct |
2 ms |
724 KB |
Output is correct |
10 |
Correct |
2 ms |
724 KB |
Output is correct |
11 |
Correct |
1 ms |
724 KB |
Output is correct |
12 |
Correct |
2 ms |
724 KB |
Output is correct |
13 |
Correct |
248 ms |
860 KB |
Output is correct |
14 |
Correct |
271 ms |
856 KB |
Output is correct |
15 |
Correct |
188 ms |
820 KB |
Output is correct |
16 |
Correct |
181 ms |
856 KB |
Output is correct |
17 |
Correct |
165 ms |
724 KB |
Output is correct |
18 |
Correct |
270 ms |
980 KB |
Output is correct |
19 |
Correct |
249 ms |
860 KB |
Output is correct |
20 |
Correct |
208 ms |
860 KB |
Output is correct |
21 |
Incorrect |
254 ms |
860 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |