#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_C"
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#include "Mylib/DataStructure/RangeTree/range_tree.cpp"
#include "Mylib/IO/input_tuples.cpp"
#include "Mylib/IO/input_tuples_with_index.cpp"
namespace hl = haar_lib;
int main() {
int n;
std::cin >> n;
hl::range_tree_builder builder;
std::map<std::pair<int, int>, int> m;
for (auto [i, x, y] : hl::input_tuples_with_index<int, int>(n)) {
builder.add(x, y);
m[{x, y}] = i;
}
auto rt = builder.build();
int q;
std::cin >> q;
for (auto [sx, tx, sy, ty] : hl::input_tuples<int, int, int, int>(q)) {
auto res = rt.get({sx, sy}, {tx + 1, ty + 1});
std::vector<int> ans;
for (auto &p : res) ans.push_back(m[p]);
std::sort(ans.begin(), ans.end());
for (auto &x : ans) {
std::cout << x << "\n";
}
std::cout << "\n";
}
return 0;
}
#line 1 "test/aoj/DSL_2_C/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_C"
#include <iostream>
#include <map>
#include <utility>
#include <vector>
#line 2 "Mylib/DataStructure/RangeTree/range_tree.cpp"
#include <algorithm>
#include <iterator>
#line 6 "Mylib/DataStructure/RangeTree/range_tree.cpp"
namespace haar_lib {
class range_tree {
using pll = std::pair<int64_t, int64_t>;
friend class range_tree_builder;
int size_;
std::vector<int64_t> c_xs_;
std::vector<std::vector<std::pair<int64_t, int>>> data_;
public:
auto get(pll s, pll t) const {
const auto [sx, sy] = s;
const auto [tx, ty] = t;
std::vector<pll> ret;
int L = std::lower_bound(c_xs_.begin(), c_xs_.end(), sx) - c_xs_.begin();
int R = std::lower_bound(c_xs_.begin(), c_xs_.end(), tx) - c_xs_.begin();
L += size_ / 2;
R += size_ / 2;
while (L < R) {
if (R & 1) {
auto &a = data_[--R];
auto it = std::lower_bound(a.begin(), a.end(), std::make_pair(sy, 0));
while (it != a.end()) {
if (it->first >= ty) break;
ret.emplace_back(c_xs_[it->second], it->first);
++it;
}
}
if (L & 1) {
auto &a = data_[L++];
auto it = std::lower_bound(a.begin(), a.end(), std::make_pair(sy, 0));
while (it != a.end()) {
if (it->first >= ty) break;
ret.emplace_back(c_xs_[it->second], it->first);
++it;
}
}
L >>= 1;
R >>= 1;
}
return ret;
}
};
class range_tree_builder {
int N_ = 0;
std::vector<int64_t> xs_, ys_;
public:
range_tree_builder() {}
void add(int64_t x, int64_t y) {
++N_;
xs_.push_back(x);
ys_.push_back(y);
}
auto build() const {
range_tree ret;
ret.c_xs_ = xs_;
std::sort(ret.c_xs_.begin(), ret.c_xs_.end());
ret.c_xs_.erase(std::unique(ret.c_xs_.begin(), ret.c_xs_.end()), ret.c_xs_.end());
int M = ret.c_xs_.size();
ret.size_ = 1 << (M > 1 ? 32 - __builtin_clz(M - 1) + 1 : 1);
ret.data_.resize(ret.size_);
for (int i = 0; i < N_; ++i) {
int j = std::lower_bound(ret.c_xs_.begin(), ret.c_xs_.end(), xs_[i]) - ret.c_xs_.begin();
ret.data_[ret.size_ / 2 + j].emplace_back(ys_[i], j);
}
for (int i = ret.size_ / 2; i < ret.size_; ++i) {
std::sort(ret.data_[i].begin(), ret.data_[i].end());
}
for (int i = ret.size_ / 2 - 1; i > 0; --i) {
auto &a = ret.data_[i << 1 | 0];
auto &b = ret.data_[i << 1 | 1];
std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(ret.data_[i]));
}
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuples.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuples.cpp"
#include <tuple>
#line 6 "Mylib/IO/input_tuple.cpp"
namespace haar_lib {
template <typename T, size_t... I>
static void input_tuple_helper(std::istream &s, T &val, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(s >> std::get<I>(val)), 0)...};
}
template <typename T, typename U>
std::istream &operator>>(std::istream &s, std::pair<T, U> &value) {
s >> value.first >> value.second;
return s;
}
template <typename... Args>
std::istream &operator>>(std::istream &s, std::tuple<Args...> &value) {
input_tuple_helper(s, value, std::make_index_sequence<sizeof...(Args)>());
return s;
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuples {
struct iter {
using value_type = std::tuple<Args...>;
value_type value;
bool fetched = false;
int N, c = 0;
value_type operator*() {
if (not fetched) {
std::cin >> value;
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuples(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples(int N) {
return InputTuples<Args...>(N);
}
} // namespace haar_lib
#line 8 "Mylib/IO/input_tuples_with_index.cpp"
namespace haar_lib {
template <typename... Args>
class InputTuplesWithIndex {
struct iter {
using value_type = std::tuple<int, Args...>;
value_type value;
bool fetched = false;
int N;
int c = 0;
value_type operator*() {
if (not fetched) {
std::tuple<Args...> temp;
std::cin >> temp;
value = std::tuple_cat(std::make_tuple(c), temp);
}
return value;
}
void operator++() {
++c;
fetched = false;
}
bool operator!=(iter &) const {
return c < N;
}
iter(int N) : N(N) {}
};
int N;
public:
InputTuplesWithIndex(int N) : N(N) {}
iter begin() const { return iter(N); }
iter end() const { return iter(N); }
};
template <typename... Args>
auto input_tuples_with_index(int N) {
return InputTuplesWithIndex<Args...>(N);
}
} // namespace haar_lib
#line 10 "test/aoj/DSL_2_C/main.test.cpp"
namespace hl = haar_lib;
int main() {
int n;
std::cin >> n;
hl::range_tree_builder builder;
std::map<std::pair<int, int>, int> m;
for (auto [i, x, y] : hl::input_tuples_with_index<int, int>(n)) {
builder.add(x, y);
m[{x, y}] = i;
}
auto rt = builder.build();
int q;
std::cin >> q;
for (auto [sx, tx, sy, ty] : hl::input_tuples<int, int, int, int>(q)) {
auto res = rt.get({sx, sy}, {tx + 1, ty + 1});
std::vector<int> ans;
for (auto &p : res) ans.push_back(m[p]);
std::sort(ans.begin(), ans.end());
for (auto &x : ans) {
std::cout << x << "\n";
}
std::cout << "\n";
}
return 0;
}
test/aoj/DSL_2_C/main.test.cpp
Input tuple
(Mylib/IO/input_tuple.cpp)