This documentation is automatically generated by competitive-verifier/competitive-verifier
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/738
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/Misc/compress.hpp"
#include "src/DataStructure/BinaryIndexedTree.hpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N, K;
cin >> N >> K;
long long A[N];
for (int i= 0; i < N; i++) cin >> A[i];
vector<long long> vec(A, A + N);
auto id= compress(vec);
BinaryIndexedTree<long long> bit1(vec.size()), bit2(vec.size());
long long sum= 0;
auto add= [&](int i, int s) {
int idx= id(A[i]);
bit1.add(idx, s), bit2.add(idx, s * A[i]), sum+= s * A[i];
};
long long ans= 1ll << 60;
for (int i= 0; i < N; i++) {
add(i, 1);
if (i >= K - 1) {
int med= bit1.find(K / 2);
int lcnt= bit1.sum(med), hcnt= K - lcnt;
long long lsum= bit2.sum(med), hsum= sum - lsum;
long long low= lcnt * vec[med] - lsum;
long long high= hsum - hcnt * vec[med];
ans= min(ans, low + high);
add(i - K + 1, -1);
}
}
cout << ans << "\n";
return 0;
}
#line 1 "test/yukicoder/738.BIT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/738
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/Misc/compress.hpp"
#include <algorithm>
template <class T> auto compress(std::vector<T> &v) {
return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
#line 4 "src/DataStructure/BinaryIndexedTree.hpp"
template <typename T> class BinaryIndexedTree {
std::vector<T> dat;
public:
BinaryIndexedTree(int n): dat(n + 1, T()) {}
BinaryIndexedTree(int n, T a): BinaryIndexedTree(std::vector<T>(n, a)) {}
BinaryIndexedTree(const std::vector<T>& y): dat(y.size() + 1, 0) {
for (int i= y.size(); i--;) dat[i + 1]= y[i];
for (int i= 1, e= dat.size(), j; i < e; ++i)
if ((j= i + (i & -i)) < e) dat[j]+= dat[i];
}
void add(int i, T a= 1) {
for (++i; i < (int)dat.size(); i+= i & -i) dat[i]+= a;
}
T sum(int i) const { // sum [0,i)
T s= 0;
for (; i; i&= i - 1) s+= dat[i];
return s;
}
T sum(int l, int r) const { return sum(r) - sum(l); } // sum [l,r)
T operator[](int k) const { return sum(k + 1) - sum(k); }
int find(T k) const { // min { i : sum(i+1) > k } -> kth element(0-indexed)
int i= 0;
for (int p= 1 << (std::__lg(dat.size() - 1) + 1), e= dat.size(); p; p>>= 1)
if (i + p < e && dat[i + p] <= k) k-= dat[i+= p];
return i + 1 == (int)dat.size() ? -1 : i; // -1 -> no solutions
}
};
#line 8 "test/yukicoder/738.BIT.test.cpp"
using namespace std;
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int N, K;
cin >> N >> K;
long long A[N];
for (int i= 0; i < N; i++) cin >> A[i];
vector<long long> vec(A, A + N);
auto id= compress(vec);
BinaryIndexedTree<long long> bit1(vec.size()), bit2(vec.size());
long long sum= 0;
auto add= [&](int i, int s) {
int idx= id(A[i]);
bit1.add(idx, s), bit2.add(idx, s * A[i]), sum+= s * A[i];
};
long long ans= 1ll << 60;
for (int i= 0; i < N; i++) {
add(i, 1);
if (i >= K - 1) {
int med= bit1.find(K / 2);
int lcnt= bit1.sum(med), hcnt= K - lcnt;
long long lsum= bit2.sum(med), hsum= sum - lsum;
long long low= lcnt * vec[med] - lsum;
long long high= hsum - hcnt * vec[med];
ans= min(ans, low + high);
add(i - K + 1, -1);
}
}
cout << ans << "\n";
return 0;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++-13 | 00_sample1.txt |
![]() |
6 ms | 4 MB |
g++-13 | 00_sample2.txt |
![]() |
5 ms | 4 MB |
g++-13 | 00_sample3.txt |
![]() |
5 ms | 4 MB |
g++-13 | 00_sample4.txt |
![]() |
5 ms | 4 MB |
g++-13 | 00_sample5.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_00.txt |
![]() |
6 ms | 4 MB |
g++-13 | 10_random_small_01.txt |
![]() |
6 ms | 4 MB |
g++-13 | 10_random_small_02.txt |
![]() |
6 ms | 4 MB |
g++-13 | 10_random_small_03.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_04.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_05.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_06.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_07.txt |
![]() |
5 ms | 4 MB |
g++-13 | 10_random_small_08.txt |
![]() |
6 ms | 4 MB |
g++-13 | 10_random_small_09.txt |
![]() |
5 ms | 4 MB |
g++-13 | 11_random_large_00.txt |
![]() |
35 ms | 6 MB |
g++-13 | 11_random_large_01.txt |
![]() |
37 ms | 6 MB |
g++-13 | 11_random_large_02.txt |
![]() |
40 ms | 6 MB |
g++-13 | 11_random_large_03.txt |
![]() |
39 ms | 6 MB |
g++-13 | 11_random_large_04.txt |
![]() |
46 ms | 6 MB |
g++-13 | 11_random_large_05.txt |
![]() |
38 ms | 6 MB |
g++-13 | 11_random_large_06.txt |
![]() |
44 ms | 6 MB |
g++-13 | 11_random_large_07.txt |
![]() |
40 ms | 6 MB |
g++-13 | 11_random_large_08.txt |
![]() |
43 ms | 6 MB |
g++-13 | 11_random_large_09.txt |
![]() |
44 ms | 6 MB |
g++-13 | 20_anti_small_00.txt |
![]() |
7 ms | 4 MB |
g++-13 | 20_anti_small_01.txt |
![]() |
6 ms | 4 MB |
g++-13 | 20_anti_small_02.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_03.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_04.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_05.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_06.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_07.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_08.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_09.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_10.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_11.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_12.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_13.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_14.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_15.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_16.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_17.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_18.txt |
![]() |
5 ms | 4 MB |
g++-13 | 20_anti_small_19.txt |
![]() |
5 ms | 4 MB |
g++-13 | 21_anti_large_00.txt |
![]() |
39 ms | 6 MB |
g++-13 | 21_anti_large_01.txt |
![]() |
38 ms | 6 MB |
g++-13 | 21_anti_large_02.txt |
![]() |
39 ms | 6 MB |
g++-13 | 21_anti_large_03.txt |
![]() |
36 ms | 6 MB |
g++-13 | 21_anti_large_04.txt |
![]() |
36 ms | 6 MB |
g++-13 | 21_anti_large_05.txt |
![]() |
37 ms | 6 MB |
g++-13 | 21_anti_large_06.txt |
![]() |
41 ms | 6 MB |
g++-13 | 21_anti_large_07.txt |
![]() |
38 ms | 6 MB |
g++-13 | 21_anti_large_08.txt |
![]() |
41 ms | 6 MB |
g++-13 | 21_anti_large_09.txt |
![]() |
40 ms | 6 MB |
g++-13 | 21_anti_large_10.txt |
![]() |
41 ms | 6 MB |
g++-13 | 21_anti_large_11.txt |
![]() |
40 ms | 6 MB |
g++-13 | 21_anti_large_12.txt |
![]() |
37 ms | 6 MB |
g++-13 | 21_anti_large_13.txt |
![]() |
39 ms | 6 MB |
g++-13 | 21_anti_large_14.txt |
![]() |
39 ms | 6 MB |
g++-13 | 21_anti_large_15.txt |
![]() |
39 ms | 6 MB |
g++-13 | 21_anti_large_16.txt |
![]() |
38 ms | 6 MB |
g++-13 | 21_anti_large_17.txt |
![]() |
36 ms | 6 MB |
g++-13 | 21_anti_large_18.txt |
![]() |
41 ms | 6 MB |
g++-13 | 21_anti_large_19.txt |
![]() |
40 ms | 6 MB |
g++-13 | 31_corners_00.txt |
![]() |
45 ms | 6 MB |
g++-13 | 31_corners_01.txt |
![]() |
47 ms | 6 MB |
g++-13 | 32_corners_00.txt |
![]() |
26 ms | 6 MB |
g++-13 | 32_corners_01.txt |
![]() |
25 ms | 6 MB |
g++-13 | 33_corners_00.txt |
![]() |
30 ms | 6 MB |
g++-13 | 33_corners_01.txt |
![]() |
28 ms | 6 MB |
g++-13 | 34_corners_00.txt |
![]() |
12 ms | 5 MB |
g++-13 | 34_corners_01.txt |
![]() |
13 ms | 5 MB |
g++-13 | 34_corners_02.txt |
![]() |
13 ms | 5 MB |
g++-13 | 34_corners_03.txt |
![]() |
13 ms | 5 MB |
g++-13 | 35_corners_00.txt |
![]() |
32 ms | 6 MB |
g++-13 | 35_corners_01.txt |
![]() |
30 ms | 6 MB |
g++-13 | 36_corners_00.txt |
![]() |
34 ms | 6 MB |
g++-13 | 36_corners_01.txt |
![]() |
37 ms | 6 MB |
g++-13 | 37_corners_00.txt |
![]() |
34 ms | 6 MB |
g++-13 | 38_corners_00.txt |
![]() |
30 ms | 6 MB |
g++-13 | 39_corners_00.txt |
![]() |
32 ms | 6 MB |
g++-13 | 40_corners_00.txt |
![]() |
33 ms | 6 MB |
g++-13 | 41_corners_00.txt |
![]() |
14 ms | 5 MB |
g++-13 | 42_corners_00.txt |
![]() |
15 ms | 5 MB |
g++-13 | 43_corners_00.txt |
![]() |
57 ms | 6 MB |
g++-13 | 44_corners_00.txt |
![]() |
52 ms | 6 MB |
g++-13 | 45_corners_00.txt |
![]() |
32 ms | 6 MB |
g++-13 | 45_corners_01.txt |
![]() |
31 ms | 6 MB |
g++-13 | 90_hand_00.txt |
![]() |
7 ms | 4 MB |
g++-13 | 90_hand_01.txt |
![]() |
5 ms | 4 MB |
g++-13 | 90_hand_02.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 00_sample1.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 00_sample2.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 00_sample3.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 00_sample4.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 00_sample5.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_00.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 10_random_small_01.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 10_random_small_02.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 10_random_small_03.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_04.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_05.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_06.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_07.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 10_random_small_08.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 10_random_small_09.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 11_random_large_00.txt |
![]() |
38 ms | 6 MB |
clang++-18 | 11_random_large_01.txt |
![]() |
39 ms | 6 MB |
clang++-18 | 11_random_large_02.txt |
![]() |
43 ms | 6 MB |
clang++-18 | 11_random_large_03.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 11_random_large_04.txt |
![]() |
49 ms | 6 MB |
clang++-18 | 11_random_large_05.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 11_random_large_06.txt |
![]() |
46 ms | 6 MB |
clang++-18 | 11_random_large_07.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 11_random_large_08.txt |
![]() |
45 ms | 6 MB |
clang++-18 | 11_random_large_09.txt |
![]() |
46 ms | 6 MB |
clang++-18 | 20_anti_small_00.txt |
![]() |
7 ms | 4 MB |
clang++-18 | 20_anti_small_01.txt |
![]() |
6 ms | 4 MB |
clang++-18 | 20_anti_small_02.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_03.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_04.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_05.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_06.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_07.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_08.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_09.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_10.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_11.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_12.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_13.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_14.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_15.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_16.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_17.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_18.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 20_anti_small_19.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 21_anti_large_00.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 21_anti_large_01.txt |
![]() |
39 ms | 6 MB |
clang++-18 | 21_anti_large_02.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 21_anti_large_03.txt |
![]() |
37 ms | 6 MB |
clang++-18 | 21_anti_large_04.txt |
![]() |
36 ms | 6 MB |
clang++-18 | 21_anti_large_05.txt |
![]() |
38 ms | 6 MB |
clang++-18 | 21_anti_large_06.txt |
![]() |
42 ms | 6 MB |
clang++-18 | 21_anti_large_07.txt |
![]() |
38 ms | 6 MB |
clang++-18 | 21_anti_large_08.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 21_anti_large_09.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 21_anti_large_10.txt |
![]() |
43 ms | 6 MB |
clang++-18 | 21_anti_large_11.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 21_anti_large_12.txt |
![]() |
37 ms | 6 MB |
clang++-18 | 21_anti_large_13.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 21_anti_large_14.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 21_anti_large_15.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 21_anti_large_16.txt |
![]() |
40 ms | 6 MB |
clang++-18 | 21_anti_large_17.txt |
![]() |
37 ms | 6 MB |
clang++-18 | 21_anti_large_18.txt |
![]() |
42 ms | 6 MB |
clang++-18 | 21_anti_large_19.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 31_corners_00.txt |
![]() |
45 ms | 6 MB |
clang++-18 | 31_corners_01.txt |
![]() |
46 ms | 6 MB |
clang++-18 | 32_corners_00.txt |
![]() |
27 ms | 6 MB |
clang++-18 | 32_corners_01.txt |
![]() |
28 ms | 6 MB |
clang++-18 | 33_corners_00.txt |
![]() |
34 ms | 6 MB |
clang++-18 | 33_corners_01.txt |
![]() |
31 ms | 6 MB |
clang++-18 | 34_corners_00.txt |
![]() |
12 ms | 5 MB |
clang++-18 | 34_corners_01.txt |
![]() |
13 ms | 5 MB |
clang++-18 | 34_corners_02.txt |
![]() |
13 ms | 5 MB |
clang++-18 | 34_corners_03.txt |
![]() |
13 ms | 5 MB |
clang++-18 | 35_corners_00.txt |
![]() |
36 ms | 6 MB |
clang++-18 | 35_corners_01.txt |
![]() |
34 ms | 6 MB |
clang++-18 | 36_corners_00.txt |
![]() |
38 ms | 6 MB |
clang++-18 | 36_corners_01.txt |
![]() |
41 ms | 6 MB |
clang++-18 | 37_corners_00.txt |
![]() |
34 ms | 7 MB |
clang++-18 | 38_corners_00.txt |
![]() |
31 ms | 6 MB |
clang++-18 | 39_corners_00.txt |
![]() |
33 ms | 6 MB |
clang++-18 | 40_corners_00.txt |
![]() |
35 ms | 6 MB |
clang++-18 | 41_corners_00.txt |
![]() |
14 ms | 5 MB |
clang++-18 | 42_corners_00.txt |
![]() |
14 ms | 5 MB |
clang++-18 | 43_corners_00.txt |
![]() |
54 ms | 6 MB |
clang++-18 | 44_corners_00.txt |
![]() |
51 ms | 6 MB |
clang++-18 | 45_corners_00.txt |
![]() |
31 ms | 6 MB |
clang++-18 | 45_corners_01.txt |
![]() |
29 ms | 6 MB |
clang++-18 | 90_hand_00.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 90_hand_01.txt |
![]() |
5 ms | 4 MB |
clang++-18 | 90_hand_02.txt |
![]() |
5 ms | 4 MB |