test/yukicoder/738.BIT.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/738

Depends on

• Binary Indexed Tree (src/DataStructure/BinaryIndexedTree.hpp)
• 座標圧縮 (src/Misc/compress.hpp)

Code

// 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;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample1.txt	AC	6 ms	4 MB
g++-13	00_sample2.txt	AC	5 ms	4 MB
g++-13	00_sample3.txt	AC	5 ms	4 MB
g++-13	00_sample4.txt	AC	5 ms	4 MB
g++-13	00_sample5.txt	AC	5 ms	4 MB
g++-13	10_random_small_00.txt	AC	6 ms	4 MB
g++-13	10_random_small_01.txt	AC	6 ms	4 MB
g++-13	10_random_small_02.txt	AC	6 ms	4 MB
g++-13	10_random_small_03.txt	AC	5 ms	4 MB
g++-13	10_random_small_04.txt	AC	5 ms	4 MB
g++-13	10_random_small_05.txt	AC	5 ms	4 MB
g++-13	10_random_small_06.txt	AC	5 ms	4 MB
g++-13	10_random_small_07.txt	AC	5 ms	4 MB
g++-13	10_random_small_08.txt	AC	6 ms	4 MB
g++-13	10_random_small_09.txt	AC	5 ms	4 MB
g++-13	11_random_large_00.txt	AC	35 ms	6 MB
g++-13	11_random_large_01.txt	AC	37 ms	6 MB
g++-13	11_random_large_02.txt	AC	40 ms	6 MB
g++-13	11_random_large_03.txt	AC	39 ms	6 MB
g++-13	11_random_large_04.txt	AC	46 ms	6 MB
g++-13	11_random_large_05.txt	AC	38 ms	6 MB
g++-13	11_random_large_06.txt	AC	44 ms	6 MB
g++-13	11_random_large_07.txt	AC	40 ms	6 MB
g++-13	11_random_large_08.txt	AC	43 ms	6 MB
g++-13	11_random_large_09.txt	AC	44 ms	6 MB
g++-13	20_anti_small_00.txt	AC	7 ms	4 MB
g++-13	20_anti_small_01.txt	AC	6 ms	4 MB
g++-13	20_anti_small_02.txt	AC	5 ms	4 MB
g++-13	20_anti_small_03.txt	AC	5 ms	4 MB
g++-13	20_anti_small_04.txt	AC	5 ms	4 MB
g++-13	20_anti_small_05.txt	AC	5 ms	4 MB
g++-13	20_anti_small_06.txt	AC	5 ms	4 MB
g++-13	20_anti_small_07.txt	AC	5 ms	4 MB
g++-13	20_anti_small_08.txt	AC	5 ms	4 MB
g++-13	20_anti_small_09.txt	AC	5 ms	4 MB
g++-13	20_anti_small_10.txt	AC	5 ms	4 MB
g++-13	20_anti_small_11.txt	AC	5 ms	4 MB
g++-13	20_anti_small_12.txt	AC	5 ms	4 MB
g++-13	20_anti_small_13.txt	AC	5 ms	4 MB
g++-13	20_anti_small_14.txt	AC	5 ms	4 MB
g++-13	20_anti_small_15.txt	AC	5 ms	4 MB
g++-13	20_anti_small_16.txt	AC	5 ms	4 MB
g++-13	20_anti_small_17.txt	AC	5 ms	4 MB
g++-13	20_anti_small_18.txt	AC	5 ms	4 MB
g++-13	20_anti_small_19.txt	AC	5 ms	4 MB
g++-13	21_anti_large_00.txt	AC	39 ms	6 MB
g++-13	21_anti_large_01.txt	AC	38 ms	6 MB
g++-13	21_anti_large_02.txt	AC	39 ms	6 MB
g++-13	21_anti_large_03.txt	AC	36 ms	6 MB
g++-13	21_anti_large_04.txt	AC	36 ms	6 MB
g++-13	21_anti_large_05.txt	AC	37 ms	6 MB
g++-13	21_anti_large_06.txt	AC	41 ms	6 MB
g++-13	21_anti_large_07.txt	AC	38 ms	6 MB
g++-13	21_anti_large_08.txt	AC	41 ms	6 MB
g++-13	21_anti_large_09.txt	AC	40 ms	6 MB
g++-13	21_anti_large_10.txt	AC	41 ms	6 MB
g++-13	21_anti_large_11.txt	AC	40 ms	6 MB
g++-13	21_anti_large_12.txt	AC	37 ms	6 MB
g++-13	21_anti_large_13.txt	AC	39 ms	6 MB
g++-13	21_anti_large_14.txt	AC	39 ms	6 MB
g++-13	21_anti_large_15.txt	AC	39 ms	6 MB
g++-13	21_anti_large_16.txt	AC	38 ms	6 MB
g++-13	21_anti_large_17.txt	AC	36 ms	6 MB
g++-13	21_anti_large_18.txt	AC	41 ms	6 MB
g++-13	21_anti_large_19.txt	AC	40 ms	6 MB
g++-13	31_corners_00.txt	AC	45 ms	6 MB
g++-13	31_corners_01.txt	AC	47 ms	6 MB
g++-13	32_corners_00.txt	AC	26 ms	6 MB
g++-13	32_corners_01.txt	AC	25 ms	6 MB
g++-13	33_corners_00.txt	AC	30 ms	6 MB
g++-13	33_corners_01.txt	AC	28 ms	6 MB
g++-13	34_corners_00.txt	AC	12 ms	5 MB
g++-13	34_corners_01.txt	AC	13 ms	5 MB
g++-13	34_corners_02.txt	AC	13 ms	5 MB
g++-13	34_corners_03.txt	AC	13 ms	5 MB
g++-13	35_corners_00.txt	AC	32 ms	6 MB
g++-13	35_corners_01.txt	AC	30 ms	6 MB
g++-13	36_corners_00.txt	AC	34 ms	6 MB
g++-13	36_corners_01.txt	AC	37 ms	6 MB
g++-13	37_corners_00.txt	AC	34 ms	6 MB
g++-13	38_corners_00.txt	AC	30 ms	6 MB
g++-13	39_corners_00.txt	AC	32 ms	6 MB
g++-13	40_corners_00.txt	AC	33 ms	6 MB
g++-13	41_corners_00.txt	AC	14 ms	5 MB
g++-13	42_corners_00.txt	AC	15 ms	5 MB
g++-13	43_corners_00.txt	AC	57 ms	6 MB
g++-13	44_corners_00.txt	AC	52 ms	6 MB
g++-13	45_corners_00.txt	AC	32 ms	6 MB
g++-13	45_corners_01.txt	AC	31 ms	6 MB
g++-13	90_hand_00.txt	AC	7 ms	4 MB
g++-13	90_hand_01.txt	AC	5 ms	4 MB
g++-13	90_hand_02.txt	AC	5 ms	4 MB
clang++-18	00_sample1.txt	AC	6 ms	4 MB
clang++-18	00_sample2.txt	AC	5 ms	4 MB
clang++-18	00_sample3.txt	AC	5 ms	4 MB
clang++-18	00_sample4.txt	AC	5 ms	4 MB
clang++-18	00_sample5.txt	AC	5 ms	4 MB
clang++-18	10_random_small_00.txt	AC	6 ms	4 MB
clang++-18	10_random_small_01.txt	AC	6 ms	4 MB
clang++-18	10_random_small_02.txt	AC	6 ms	4 MB
clang++-18	10_random_small_03.txt	AC	5 ms	4 MB
clang++-18	10_random_small_04.txt	AC	5 ms	4 MB
clang++-18	10_random_small_05.txt	AC	5 ms	4 MB
clang++-18	10_random_small_06.txt	AC	5 ms	4 MB
clang++-18	10_random_small_07.txt	AC	5 ms	4 MB
clang++-18	10_random_small_08.txt	AC	6 ms	4 MB
clang++-18	10_random_small_09.txt	AC	5 ms	4 MB
clang++-18	11_random_large_00.txt	AC	38 ms	6 MB
clang++-18	11_random_large_01.txt	AC	39 ms	6 MB
clang++-18	11_random_large_02.txt	AC	43 ms	6 MB
clang++-18	11_random_large_03.txt	AC	41 ms	6 MB
clang++-18	11_random_large_04.txt	AC	49 ms	6 MB
clang++-18	11_random_large_05.txt	AC	40 ms	6 MB
clang++-18	11_random_large_06.txt	AC	46 ms	6 MB
clang++-18	11_random_large_07.txt	AC	40 ms	6 MB
clang++-18	11_random_large_08.txt	AC	45 ms	6 MB
clang++-18	11_random_large_09.txt	AC	46 ms	6 MB
clang++-18	20_anti_small_00.txt	AC	7 ms	4 MB
clang++-18	20_anti_small_01.txt	AC	6 ms	4 MB
clang++-18	20_anti_small_02.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_03.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_04.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_05.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_06.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_07.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_08.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_09.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_10.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_11.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_12.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_13.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_14.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_15.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_16.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_17.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_18.txt	AC	5 ms	4 MB
clang++-18	20_anti_small_19.txt	AC	5 ms	4 MB
clang++-18	21_anti_large_00.txt	AC	40 ms	6 MB
clang++-18	21_anti_large_01.txt	AC	39 ms	6 MB
clang++-18	21_anti_large_02.txt	AC	41 ms	6 MB
clang++-18	21_anti_large_03.txt	AC	37 ms	6 MB
clang++-18	21_anti_large_04.txt	AC	36 ms	6 MB
clang++-18	21_anti_large_05.txt	AC	38 ms	6 MB
clang++-18	21_anti_large_06.txt	AC	42 ms	6 MB
clang++-18	21_anti_large_07.txt	AC	38 ms	6 MB
clang++-18	21_anti_large_08.txt	AC	41 ms	6 MB
clang++-18	21_anti_large_09.txt	AC	41 ms	6 MB
clang++-18	21_anti_large_10.txt	AC	43 ms	6 MB
clang++-18	21_anti_large_11.txt	AC	41 ms	6 MB
clang++-18	21_anti_large_12.txt	AC	37 ms	6 MB
clang++-18	21_anti_large_13.txt	AC	40 ms	6 MB
clang++-18	21_anti_large_14.txt	AC	40 ms	6 MB
clang++-18	21_anti_large_15.txt	AC	40 ms	6 MB
clang++-18	21_anti_large_16.txt	AC	40 ms	6 MB
clang++-18	21_anti_large_17.txt	AC	37 ms	6 MB
clang++-18	21_anti_large_18.txt	AC	42 ms	6 MB
clang++-18	21_anti_large_19.txt	AC	41 ms	6 MB
clang++-18	31_corners_00.txt	AC	45 ms	6 MB
clang++-18	31_corners_01.txt	AC	46 ms	6 MB
clang++-18	32_corners_00.txt	AC	27 ms	6 MB
clang++-18	32_corners_01.txt	AC	28 ms	6 MB
clang++-18	33_corners_00.txt	AC	34 ms	6 MB
clang++-18	33_corners_01.txt	AC	31 ms	6 MB
clang++-18	34_corners_00.txt	AC	12 ms	5 MB
clang++-18	34_corners_01.txt	AC	13 ms	5 MB
clang++-18	34_corners_02.txt	AC	13 ms	5 MB
clang++-18	34_corners_03.txt	AC	13 ms	5 MB
clang++-18	35_corners_00.txt	AC	36 ms	6 MB
clang++-18	35_corners_01.txt	AC	34 ms	6 MB
clang++-18	36_corners_00.txt	AC	38 ms	6 MB
clang++-18	36_corners_01.txt	AC	41 ms	6 MB
clang++-18	37_corners_00.txt	AC	34 ms	7 MB
clang++-18	38_corners_00.txt	AC	31 ms	6 MB
clang++-18	39_corners_00.txt	AC	33 ms	6 MB
clang++-18	40_corners_00.txt	AC	35 ms	6 MB
clang++-18	41_corners_00.txt	AC	14 ms	5 MB
clang++-18	42_corners_00.txt	AC	14 ms	5 MB
clang++-18	43_corners_00.txt	AC	54 ms	6 MB
clang++-18	44_corners_00.txt	AC	51 ms	6 MB
clang++-18	45_corners_00.txt	AC	31 ms	6 MB
clang++-18	45_corners_01.txt	AC	29 ms	6 MB
clang++-18	90_hand_00.txt	AC	5 ms	4 MB
clang++-18	90_hand_01.txt	AC	5 ms	4 MB
clang++-18	90_hand_02.txt	AC	5 ms	4 MB

Back to top page