Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using std::cin;
- using std::cout;
- using std::endl;
- using std::vector;
- using std::string;
- using std::swap;
- using std::pair;
- using std::min;
- using std::max;
- using pii = pair<int, int>;
- pii merge(const pii& l, const pii& r, const vector<int> &a) {
- pii ret = {-1, -1};
- vector<int> inds = {l.first, l.second, r.first, r.second};
- vector<pii> elements;
- for (auto i : inds) {
- if (i != -1) {
- bool in = false;
- for (auto el : elements) {
- if (el.first == a[i] && el.second == i) {
- in = true;
- break;
- }
- }
- if (!in) {
- elements.push_back((pii){a[i], i});
- }
- }
- }
- std::sort(elements.begin(), elements.end());
- ret.first = elements[0].second;
- if (elements.size() >= 2) {
- ret.second = elements[1].second;
- }
- return ret;
- }
- int main() {
- std::ios_base::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- int n, m;
- cin >> n >> m;
- vector<int> a(n);
- for (int i = 0; i < n; ++i) cin >> a[i];
- vector<int> pow;
- for (int p = 1; p <= n; p <<= 1) {
- pow.push_back(p);
- }
- vector<int> find_p(n + 1);
- int deg = 0;
- for (int i = 1; i <= n; ++i) {
- if (pow[deg] * 2 <= i) {
- ++deg;
- }
- find_p[i] = deg;
- }
- vector<vector<pii> > sparse_table(pow.size());
- for (int p = 0; p < pow.size(); ++p) {
- for (int i = 0; i + pow[p] <= n; ++i) {
- if (p == 0) {
- sparse_table[p].push_back({i, -1});
- } else {
- pii left = sparse_table[p - 1][i];
- pii right = sparse_table[p - 1][i + pow[p - 1]];
- sparse_table[p].push_back(merge(left, right, a));
- }
- }
- }
- while (m--) {
- int l, r;
- cin >> l >> r;
- l--;
- int p = find_p[r - l];
- pii left = sparse_table[p][l];
- pii right = sparse_table[p][r - pow[p]];
- int res = merge(left, right, a).second;
- if (res == -1) {
- cout << res << '\n';
- } else {
- cout << a[res] << '\n';
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement