Kyselyt

input/code.cpp: In function 'int main()':
input/code.cpp:39:10: warning: variable 'summataulu_result' set but not used [-Wunused-but-set-variable]
   39 |     auto summataulu_result = [&](int a, int b) {
      |          ^~~~~~~~~~~~~~~~~

#include <bits/stdc++.h>

using namespace std;

constexpr int N = (1 << 17);

int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
int parent(int i) { return i / 2; }
int is_left(int i) { return (~i) & 1; }
int is_right(int i) { return i & 1; }
int is_root(int i) { return i == 1; }
int is_leaf(int i) { return i >= N; }

int main() {
    ios::sync_with_stdio(false);
    int n, q;
    cin >> n >> q;
    vector<int> luvut(n+1, -1);
    vector<int> yli_puolet(N + (n+2), -1);
    unordered_map<int, map<int, int>> summataulu;
    map<int, int> määrätaulu;

    summataulu[-1][0] = 0;
    summataulu[-1][N+1] = 0;

    auto summataulu_range_sum = [&](int luku, int a, int b) {
        auto it_a = prev(summataulu[luku].lower_bound(a));
        auto it_b = prev(summataulu[luku].upper_bound(b));
        int val_a = it_a->second;
        int val_b = it_b->second;
        return val_b - val_a;
    };

    auto summataulu_yli_puolet = [&](int luku, int a0, int b0) {
        return luku != -1 && summataulu_range_sum(luku, a0, b0) > (b0 - a0 + 1) / 2;
    };

    auto summataulu_result = [&](int a, int b) {
        int puolet = (b - a + 1) / 2;
        for (auto x: määrätaulu) {
            if (x.second > puolet && summataulu_yli_puolet(x.first, a, b)) {
                return x.first;
            }
        }
        return -1;
    };

    auto binary_tree_result = [&](int a0, int b0) {
        int a = a0 + N, b = b0 + N;
        unordered_set<int> tutkitut;
        auto tutki = [&](int x) {
            if (!tutkitut.count(x) && summataulu_yli_puolet(x, a0, b0)) {
                return true;
            }
            tutkitut.insert(x);
            return false;
        };
        while (a <= b) {
            if (is_right(a)) {
                if (tutki(yli_puolet[a])) {
                    return yli_puolet[a];
                }
                a++;
            }
            if (is_left(b)) {
                if (tutki(yli_puolet[b])) {
                    return yli_puolet[b];
                }
                b--;
            }
            a = parent(a);
            b = parent(b);
        }
        return -1;
    };

    auto binary_tree_set = [&](int pos, int val) {
        int mask = 0;
        int i = pos + N;
        yli_puolet[i] = val;
        while ((i = parent(i))) {
            mask = 2 * mask + 1;
            int res_a = yli_puolet[left(i)];
            int res_b = yli_puolet[right(i)];
            int a = pos & ~mask, b = pos | mask;
            if (res_a == res_b || summataulu_yli_puolet(res_a, a, b)) {
                yli_puolet[i] = res_a;
            } else if (summataulu_yli_puolet(res_b, a, b)) {
                yli_puolet[i] = res_b;
            } else {
                yli_puolet[i] = -1;
            }
        }
    };

    for (int i = 1; i <= n; i++) {
        cin >> luvut[i];
        summataulu[luvut[i]][i] = 1;
        määrätaulu[luvut[i]] += 1;
    }
    for (auto& rivi : summataulu) {
        rivi.second[0] = 0;
        rivi.second[N+1] = 0;
        auto i = rivi.second.begin();
        int edellinen = 0;
        while (i != rivi.second.end()) {
            i->second += edellinen;
            edellinen = i->second;
            i++;
        }
    }
    for (int i = 1; i <= n; i++) {
        binary_tree_set(i, luvut[i]);
    }

    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        int vastaus = binary_tree_result(a, b);
        cout << vastaus << "\n";
    }
}

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

Test 3

Group: 1, 3, 4

Verdict: ACCEPTED

Test 4

Group: 2, 3, 4

Verdict: ACCEPTED

Test 5

Group: 2, 3, 4

Verdict: ACCEPTED

Test 6

Group: 2, 3, 4

Verdict: ACCEPTED

Test 7

Group: 3, 4

Verdict: ACCEPTED

Test 8

Group: 4

Verdict: ACCEPTED

Test 9

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4

Verdict: ACCEPTED

Test 12

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 3, 4

Verdict: ACCEPTED

Test 14

Group: 4

Verdict: WRONG ANSWER

Test 15

Group: 4

Verdict: WRONG ANSWER

Test 16

Group: 4

Verdict: TIME LIMIT EXCEEDED