test/yukicoder/649.BIT.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://yukicoder.me/problems/no/649

Depends on

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

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/649
// 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 Q, K;
 cin >> Q >> K;
 K--;
 vector<long long> query, x;
 while (Q--) {
  long long v;
  cin >> v;
  if (v == 1) cin >> v, x.push_back(v);
  else v= -1;
  query.push_back(v);
 }
 auto id= compress(x);
 BinaryIndexedTree<long long> bit(x.size());
 for (auto q: query)
  if (q < 0) {
   if (int i= bit.find(K); i >= 0) cout << x[i] << '\n', bit.add(i, -1);
   else cout << -1 << '\n';
  } else bit.add(id(q), 1);
 return 0;
}

#line 1 "test/yukicoder/649.BIT.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/649
// 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/649.BIT.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int Q, K;
 cin >> Q >> K;
 K--;
 vector<long long> query, x;
 while (Q--) {
  long long v;
  cin >> v;
  if (v == 1) cin >> v, x.push_back(v);
  else v= -1;
  query.push_back(v);
 }
 auto id= compress(x);
 BinaryIndexedTree<long long> bit(x.size());
 for (auto q: query)
  if (q < 0) {
   if (int i= bit.find(K); i >= 0) cout << x[i] << '\n', bit.add(i, -1);
   else cout << -1 << '\n';
  } else bit.add(id(q), 1);
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	corner1.txt	AC	7 ms	4 MB
g++-13	corner2.txt	AC	6 ms	4 MB
g++-13	corner3.txt	AC	6 ms	4 MB
g++-13	corner4.txt	AC	22 ms	5 MB
g++-13	corner5.txt	AC	46 ms	8 MB
g++-13	corner6.txt	AC	48 ms	8 MB
g++-13	corner7.txt	AC	35 ms	7 MB
g++-13	normal1.txt	AC	6 ms	4 MB
g++-13	normal2.txt	AC	6 ms	4 MB
g++-13	normal3.txt	AC	6 ms	4 MB
g++-13	normal4.txt	AC	6 ms	4 MB
g++-13	normal5.txt	AC	6 ms	3 MB
g++-13	random_large1.txt	AC	37 ms	6 MB
g++-13	random_large10.txt	AC	53 ms	7 MB
g++-13	random_large11.txt	AC	56 ms	7 MB
g++-13	random_large12.txt	AC	61 ms	7 MB
g++-13	random_large13.txt	AC	65 ms	7 MB
g++-13	random_large14.txt	AC	70 ms	8 MB
g++-13	random_large15.txt	AC	71 ms	9 MB
g++-13	random_large2.txt	AC	38 ms	6 MB
g++-13	random_large3.txt	AC	37 ms	6 MB
g++-13	random_large4.txt	AC	37 ms	6 MB
g++-13	random_large5.txt	AC	37 ms	6 MB
g++-13	random_large6.txt	AC	39 ms	6 MB
g++-13	random_large7.txt	AC	42 ms	6 MB
g++-13	random_large8.txt	AC	46 ms	6 MB
g++-13	random_large9.txt	AC	49 ms	6 MB
g++-13	random_small1.txt	AC	6 ms	4 MB
g++-13	random_small2.txt	AC	6 ms	4 MB
g++-13	random_small3.txt	AC	6 ms	4 MB
g++-13	random_small4.txt	AC	33 ms	5 MB
g++-13	random_small5.txt	AC	32 ms	5 MB
g++-13	sample1.txt	AC	7 ms	4 MB
g++-13	sample2.txt	AC	6 ms	4 MB
g++-13	sample3.txt	AC	6 ms	4 MB
g++-13	sample4.txt	AC	6 ms	4 MB
clang++-18	corner1.txt	AC	7 ms	4 MB
clang++-18	corner2.txt	AC	6 ms	4 MB
clang++-18	corner3.txt	AC	6 ms	4 MB
clang++-18	corner4.txt	AC	21 ms	6 MB
clang++-18	corner5.txt	AC	46 ms	8 MB
clang++-18	corner6.txt	AC	47 ms	8 MB
clang++-18	corner7.txt	AC	37 ms	7 MB
clang++-18	normal1.txt	AC	6 ms	4 MB
clang++-18	normal2.txt	AC	6 ms	4 MB
clang++-18	normal3.txt	AC	6 ms	4 MB
clang++-18	normal4.txt	AC	6 ms	4 MB
clang++-18	normal5.txt	AC	6 ms	4 MB
clang++-18	random_large1.txt	AC	37 ms	6 MB
clang++-18	random_large10.txt	AC	55 ms	7 MB
clang++-18	random_large11.txt	AC	57 ms	7 MB
clang++-18	random_large12.txt	AC	61 ms	7 MB
clang++-18	random_large13.txt	AC	64 ms	7 MB
clang++-18	random_large14.txt	AC	69 ms	8 MB
clang++-18	random_large15.txt	AC	72 ms	8 MB
clang++-18	random_large2.txt	AC	39 ms	6 MB
clang++-18	random_large3.txt	AC	37 ms	6 MB
clang++-18	random_large4.txt	AC	37 ms	6 MB
clang++-18	random_large5.txt	AC	36 ms	6 MB
clang++-18	random_large6.txt	AC	39 ms	6 MB
clang++-18	random_large7.txt	AC	42 ms	6 MB
clang++-18	random_large8.txt	AC	46 ms	6 MB
clang++-18	random_large9.txt	AC	50 ms	7 MB
clang++-18	random_small1.txt	AC	6 ms	4 MB
clang++-18	random_small2.txt	AC	6 ms	4 MB
clang++-18	random_small3.txt	AC	6 ms	4 MB
clang++-18	random_small4.txt	AC	32 ms	5 MB
clang++-18	random_small5.txt	AC	32 ms	5 MB
clang++-18	sample1.txt	AC	6 ms	4 MB
clang++-18	sample2.txt	AC	6 ms	4 MB
clang++-18	sample3.txt	AC	6 ms	4 MB
clang++-18	sample4.txt	AC	6 ms	4 MB

Back to top page