Hashiryo's Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub hashiryo/Library

:heavy_check_mark: test/yukicoder/649.BIT.test.cpp

Depends on

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