Kyselyt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int n, q;
int startpos[101], counts[101];
vector<int> xx;

bool accept_slice(int i1, int i2, int len) {
    while (len > 0) {
        int x1 = xx[i1], x2 = xx[i2];
        if (x1 * 2 > x2) {
            return false;
        }
        int c1 = counts[x1] - (i1 - startpos[x1]);
        int c2 = counts[x2] - (i2 - startpos[x2]);
        int c = min(c1, c2);
        i1 += c;
        i2 += c;
        len -= c;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    xx.resize(n);
    for (int& i: xx) {
        cin >> i;
    }
    vector<pii> qq(q);

    for (auto& a: qq) {
        cin >> a.first >> a.second;
        a.first -= 1;
    }

    if (xx[n-1] <= 100) {
        for (int i = n; i--;) {
            startpos[xx[i]] = i;
            counts[xx[i]] += 1;
        }
        for (auto query: qq) {
            int a = query.first, b = query.second;
            int slice_min = 0, slice_max = (b - a + 2) / 2;
            while (slice_min + 1 < slice_max) {
                int slice = (slice_min + slice_max) / 2;
                if (accept_slice(a, b - slice, slice)) {
                    slice_min = slice;
                } else {
                    slice_max = slice;
                }
            }
            cout << slice_min << "\n";
        }
    }

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED