This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/919
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/DataStructure/WaveletMatrix.hpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N;
cin >> N;
vector<int> A(N);
for (int i= 0; i < N; i++) cin >> A[i];
WaveletMatrix wm(A);
long long ans= 0;
for (int K= 1; K <= N; K++) {
int M= N / K, med= (K - 1) / 2;
long long L[M + 1], R[M + 1], Lsum= 0, Rsum= 0;
L[0]= R[0]= 0;
for (int i= 1; i <= M; i++) {
Lsum+= wm.kth_smallest(K * (i - 1), K * i, med);
Rsum+= wm.kth_smallest(N - K * i, N - K * (i - 1), med);
L[i]= max(L[i - 1], Lsum);
R[i]= max(R[i - 1], Rsum);
}
for (int i= 0; i <= M; i++) ans= max(ans, (L[i] + R[M - i]) * K);
}
cout << ans << "\n";
return 0;
}
#line 1 "test/yukicoder/919.WM.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/919
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/DataStructure/WaveletMatrix.hpp"
#include <algorithm>
#include <array>
#include <cassert>
template <class T> class WaveletMatrix {
struct SuccinctIndexableDictionary {
int len, blocks, zeros= 0;
std::vector<unsigned> bit, sum;
SuccinctIndexableDictionary(int len): len(len), blocks((len >> 5) + 1), bit(blocks, 0), sum(blocks, 0) {}
void set(int k) { bit[k >> 5]|= 1U << (k & 31); }
void build() {
for (int i= 1; i < blocks; ++i) sum[i]= sum[i - 1] + __builtin_popcount(bit[i - 1]);
zeros= rank0(len);
}
bool operator[](int k) const { return (bit[k >> 5] >> (k & 31)) & 1; }
int rank(int k) const { return (sum[k >> 5] + __builtin_popcount(bit[k >> 5] & ((1U << (k & 31)) - 1))); }
int rank0(int k) const { return k - rank(k); }
};
int len, lg;
std::vector<SuccinctIndexableDictionary> mat;
std::vector<T> vec;
public:
WaveletMatrix(const std::vector<T> &v): len(v.size()), lg(len ? 32 - __builtin_clz(len) : 1), mat(lg, SuccinctIndexableDictionary(len)), vec(v) {
std::sort(vec.begin(), vec.end()), vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
std::vector<unsigned> cur(len), nex(len);
for (int i= len; i--;) cur[i]= std::lower_bound(vec.begin(), vec.end(), v[i]) - vec.begin();
for (auto h= lg; h--; cur.swap(nex)) {
for (int i= 0; i < len; ++i)
if ((cur[i] >> h) & 1) mat[h].set(i);
mat[h].build();
std::array it{nex.begin(), nex.begin() + mat[h].zeros};
for (int i= 0; i < len; ++i) *it[mat[h][i]]++= cur[i];
}
}
// k-th(0-indexed) smallest number in v[l,r)
T kth_smallest(int l, int r, int k) const {
assert(k < r - l);
int ret= 0;
for (auto h= lg; h--;)
if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); k >= r0 - l0) k-= r0 - l0, ret|= 1 << h, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0;
else l= l0, r= r0;
return vec[ret];
}
// k-th(0-indexed) largest number in v[l,r)
T kth_largest(int l, int r, int k) const { return kth_smallest(l, r, r - l - k - 1); }
// count i s.t. (l <= i < r) && (v[i] < ub)
int count(int l, int r, T ub) const {
unsigned x= std::lower_bound(vec.begin(), vec.end(), ub) - vec.begin();
if (x >= 1u << lg) return r - l;
if (x == 0) return 0;
int ret= 0;
for (auto h= lg; h--;)
if (auto l0= mat[h].rank0(l), r0= mat[h].rank0(r); (x >> h) & 1) ret+= r0 - l0, l+= mat[h].zeros - l0, r+= mat[h].zeros - r0;
else l= l0, r= r0;
return ret;
}
// count i s.t. (l <= i < r) && (lb <= v[i] < ub)
int count(int l, int r, T lb, T ub) const { return count(l, r, ub) - count(l, r, lb); }
};
#line 7 "test/yukicoder/919.WM.test.cpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N;
cin >> N;
vector<int> A(N);
for (int i= 0; i < N; i++) cin >> A[i];
WaveletMatrix wm(A);
long long ans= 0;
for (int K= 1; K <= N; K++) {
int M= N / K, med= (K - 1) / 2;
long long L[M + 1], R[M + 1], Lsum= 0, Rsum= 0;
L[0]= R[0]= 0;
for (int i= 1; i <= M; i++) {
Lsum+= wm.kth_smallest(K * (i - 1), K * i, med);
Rsum+= wm.kth_smallest(N - K * i, N - K * (i - 1), med);
L[i]= max(L[i - 1], Lsum);
R[i]= max(R[i - 1], Rsum);
}
for (int i= 0; i <= M; i++) ans= max(ans, (L[i] + R[M - i]) * K);
}
cout << ans << "\n";
return 0;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++-13 | 99_system_test1.txt |
![]() |
18 ms | 4 MB |
g++-13 | handmade1_1.txt |
![]() |
6 ms | 4 MB |
g++-13 | handmade1_2.txt |
![]() |
5 ms | 4 MB |
g++-13 | handmade1_3.txt |
![]() |
5 ms | 4 MB |
g++-13 | handmade2_1.txt |
![]() |
7 ms | 4 MB |
g++-13 | handmade2_2.txt |
![]() |
7 ms | 4 MB |
g++-13 | handmade3_1.txt |
![]() |
5 ms | 4 MB |
g++-13 | handmade3_2.txt |
![]() |
12 ms | 4 MB |
g++-13 | handmade4_1.txt |
![]() |
7 ms | 4 MB |
g++-13 | handmade4_2.txt |
![]() |
6 ms | 4 MB |
g++-13 | handmade5_1.txt |
![]() |
7 ms | 4 MB |
g++-13 | handmade5_2.txt |
![]() |
7 ms | 4 MB |
g++-13 | handmade5_3.txt |
![]() |
5 ms | 4 MB |
g++-13 | handmade5_4.txt |
![]() |
8 ms | 4 MB |
g++-13 | handmade5_5.txt |
![]() |
5 ms | 4 MB |
g++-13 | handmade5_6.txt |
![]() |
6 ms | 4 MB |
g++-13 | handmade5_7.txt |
![]() |
9 ms | 4 MB |
g++-13 | handmade6_1.txt |
![]() |
15 ms | 4 MB |
g++-13 | handmade6_2.txt |
![]() |
16 ms | 4 MB |
g++-13 | handmade6_3.txt |
![]() |
16 ms | 4 MB |
g++-13 | handmade6_4.txt |
![]() |
24 ms | 4 MB |
g++-13 | handmade7_1.txt |
![]() |
17 ms | 4 MB |
g++-13 | large1_1.txt |
![]() |
13 ms | 4 MB |
g++-13 | large1_2.txt |
![]() |
14 ms | 4 MB |
g++-13 | large1_3.txt |
![]() |
14 ms | 4 MB |
g++-13 | large1_4.txt |
![]() |
14 ms | 4 MB |
g++-13 | large2_1.txt |
![]() |
24 ms | 4 MB |
g++-13 | large2_2.txt |
![]() |
22 ms | 4 MB |
g++-13 | large2_3.txt |
![]() |
27 ms | 4 MB |
g++-13 | large2_4.txt |
![]() |
17 ms | 4 MB |
g++-13 | large2_5.txt |
![]() |
17 ms | 4 MB |
g++-13 | large2_6.txt |
![]() |
16 ms | 4 MB |
g++-13 | large2_7.txt |
![]() |
16 ms | 4 MB |
g++-13 | max1_1.txt |
![]() |
14 ms | 4 MB |
g++-13 | max1_2.txt |
![]() |
14 ms | 4 MB |
g++-13 | max2_1.txt |
![]() |
26 ms | 4 MB |
g++-13 | max2_2.txt |
![]() |
27 ms | 4 MB |
g++-13 | max2_3.txt |
![]() |
27 ms | 4 MB |
g++-13 | max2_4.txt |
![]() |
27 ms | 4 MB |
g++-13 | middle1_1.txt |
![]() |
7 ms | 4 MB |
g++-13 | middle1_2.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_3.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_4.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_5.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_6.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_7.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle1_8.txt |
![]() |
6 ms | 4 MB |
g++-13 | middle2_1.txt |
![]() |
13 ms | 4 MB |
g++-13 | middle2_2.txt |
![]() |
13 ms | 4 MB |
g++-13 | middle2_3.txt |
![]() |
14 ms | 4 MB |
g++-13 | middle2_4.txt |
![]() |
13 ms | 4 MB |
g++-13 | rand1_1.txt |
![]() |
13 ms | 4 MB |
g++-13 | rand1_2.txt |
![]() |
11 ms | 4 MB |
g++-13 | rand1_3.txt |
![]() |
13 ms | 4 MB |
g++-13 | rand1_4.txt |
![]() |
6 ms | 4 MB |
g++-13 | sample1_1.txt |
![]() |
5 ms | 4 MB |
g++-13 | sample1_2.txt |
![]() |
5 ms | 4 MB |
g++-13 | sample1_3.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 99_system_test1.txt |
![]() |
18 ms | 4 MB |
clang++-18 | handmade1_1.txt |
![]() |
6 ms | 4 MB |
clang++-18 | handmade1_2.txt |
![]() |
5 ms | 4 MB |
clang++-18 | handmade1_3.txt |
![]() |
5 ms | 4 MB |
clang++-18 | handmade2_1.txt |
![]() |
7 ms | 4 MB |
clang++-18 | handmade2_2.txt |
![]() |
7 ms | 4 MB |
clang++-18 | handmade3_1.txt |
![]() |
5 ms | 4 MB |
clang++-18 | handmade3_2.txt |
![]() |
13 ms | 4 MB |
clang++-18 | handmade4_1.txt |
![]() |
7 ms | 4 MB |
clang++-18 | handmade4_2.txt |
![]() |
6 ms | 4 MB |
clang++-18 | handmade5_1.txt |
![]() |
7 ms | 4 MB |
clang++-18 | handmade5_2.txt |
![]() |
7 ms | 4 MB |
clang++-18 | handmade5_3.txt |
![]() |
5 ms | 4 MB |
clang++-18 | handmade5_4.txt |
![]() |
8 ms | 4 MB |
clang++-18 | handmade5_5.txt |
![]() |
5 ms | 4 MB |
clang++-18 | handmade5_6.txt |
![]() |
6 ms | 4 MB |
clang++-18 | handmade5_7.txt |
![]() |
9 ms | 4 MB |
clang++-18 | handmade6_1.txt |
![]() |
16 ms | 4 MB |
clang++-18 | handmade6_2.txt |
![]() |
16 ms | 4 MB |
clang++-18 | handmade6_3.txt |
![]() |
17 ms | 4 MB |
clang++-18 | handmade6_4.txt |
![]() |
25 ms | 4 MB |
clang++-18 | handmade7_1.txt |
![]() |
18 ms | 4 MB |
clang++-18 | large1_1.txt |
![]() |
14 ms | 4 MB |
clang++-18 | large1_2.txt |
![]() |
13 ms | 4 MB |
clang++-18 | large1_3.txt |
![]() |
14 ms | 4 MB |
clang++-18 | large1_4.txt |
![]() |
13 ms | 4 MB |
clang++-18 | large2_1.txt |
![]() |
24 ms | 4 MB |
clang++-18 | large2_2.txt |
![]() |
21 ms | 4 MB |
clang++-18 | large2_3.txt |
![]() |
26 ms | 4 MB |
clang++-18 | large2_4.txt |
![]() |
16 ms | 4 MB |
clang++-18 | large2_5.txt |
![]() |
16 ms | 4 MB |
clang++-18 | large2_6.txt |
![]() |
16 ms | 4 MB |
clang++-18 | large2_7.txt |
![]() |
16 ms | 4 MB |
clang++-18 | max1_1.txt |
![]() |
14 ms | 4 MB |
clang++-18 | max1_2.txt |
![]() |
15 ms | 4 MB |
clang++-18 | max2_1.txt |
![]() |
26 ms | 4 MB |
clang++-18 | max2_2.txt |
![]() |
28 ms | 4 MB |
clang++-18 | max2_3.txt |
![]() |
28 ms | 4 MB |
clang++-18 | max2_4.txt |
![]() |
28 ms | 4 MB |
clang++-18 | middle1_1.txt |
![]() |
7 ms | 4 MB |
clang++-18 | middle1_2.txt |
![]() |
7 ms | 4 MB |
clang++-18 | middle1_3.txt |
![]() |
6 ms | 4 MB |
clang++-18 | middle1_4.txt |
![]() |
6 ms | 4 MB |
clang++-18 | middle1_5.txt |
![]() |
6 ms | 4 MB |
clang++-18 | middle1_6.txt |
![]() |
7 ms | 4 MB |
clang++-18 | middle1_7.txt |
![]() |
6 ms | 4 MB |
clang++-18 | middle1_8.txt |
![]() |
7 ms | 4 MB |
clang++-18 | middle2_1.txt |
![]() |
14 ms | 4 MB |
clang++-18 | middle2_2.txt |
![]() |
14 ms | 4 MB |
clang++-18 | middle2_3.txt |
![]() |
15 ms | 4 MB |
clang++-18 | middle2_4.txt |
![]() |
14 ms | 4 MB |
clang++-18 | rand1_1.txt |
![]() |
13 ms | 4 MB |
clang++-18 | rand1_2.txt |
![]() |
11 ms | 4 MB |
clang++-18 | rand1_3.txt |
![]() |
13 ms | 4 MB |
clang++-18 | rand1_4.txt |
![]() |
6 ms | 4 MB |
clang++-18 | sample1_1.txt |
![]() |
5 ms | 4 MB |
clang++-18 | sample1_2.txt |
![]() |
5 ms | 4 MB |
clang++-18 | sample1_3.txt |
![]() |
5 ms | 4 MB |