test/range_kth_smallest.test.cpp

• View this file on GitHub
• Last update: 2025-05-28 17:58:43+09:00
• Problem: https://judge.yosupo.jp/problem/range_kth_smallest

Depends on

• data_structure/wavelet_matrix.hpp
• data_structure/wavelet_matrix/small.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/range_kth_smallest"

#include <data_structure/wavelet_matrix.hpp>        // for WaveletMatrix
#include <data_structure/wavelet_matrix/small.hpp>  // for WaveletMatrix::small
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <fastio/vector/read.hpp>                   // for operator>>
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>                                   // for vector
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;
    WaveletMatrix<int> wm(a);
    rep(_, q) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << wm.small(l, r, k) << endl;
    }
}

#line 1 "test/range_kth_smallest.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/range_kth_smallest"

#include <data_structure/wavelet_matrix.hpp>        // for WaveletMatrix
#include <data_structure/wavelet_matrix/small.hpp>  // for WaveletMatrix::small
#include <fastio/base.hpp>                          // for FASTIO, cin, cout
#include <fastio/char/write.hpp>                    // for operator<<
#include <fastio/signed/read.hpp>                   // for operator>>
#include <fastio/signed/write.hpp>                  // for operator<<
#include <fastio/vector/read.hpp>                   // for operator>>
#include <templates/macro/abbrev/endl.hpp>          // for endl
#include <templates/rep.hpp>                        // for rep
#include <templates/template.hpp>
#include <vector>                                   // for vector
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    cin >> a;
    WaveletMatrix<int> wm(a);
    rep(_, q) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << wm.small(l, r, k) << endl;
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_zero_00	AC	53 ms	4 MB
g++	dense_large_a_00	AC	179 ms	7 MB
g++	dense_small_a_00	AC	35 ms	6 MB
g++	example_00	AC	5 ms	4 MB
g++	max_random_00	AC	361 ms	15 MB
g++	max_random_01	AC	343 ms	15 MB
g++	max_random_02	AC	341 ms	15 MB
g++	max_random_03	AC	341 ms	15 MB
g++	max_random_04	AC	341 ms	15 MB
g++	random_00	AC	239 ms	12 MB
g++	random_01	AC	252 ms	12 MB
g++	random_02	AC	155 ms	10 MB
g++	random_03	AC	112 ms	10 MB
g++	random_04	AC	111 ms	7 MB
g++	small_00	AC	5 ms	4 MB
g++	small_01	AC	4 ms	4 MB
g++	small_02	AC	5 ms	4 MB
g++	small_03	AC	5 ms	4 MB
g++	small_04	AC	5 ms	4 MB
g++	small_05	AC	5 ms	4 MB
g++	small_06	AC	5 ms	4 MB
g++	small_07	AC	5 ms	4 MB
g++	small_08	AC	5 ms	4 MB
g++	small_09	AC	5 ms	4 MB

Back to top page