Kyselyt

#include <algorithm>
#include <array>
#include <iostream>
#include <climits>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <vector>

using namespace std;

constexpr int C = 101;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> T(n);
    for(int& val : T) {
        cin >> val;
    }

    vector<int> eka;
    for(int i = 0; i < n; ++i) {
        int val = T[i];
        while((int)eka.size() <= val) {
            eka.push_back(i);
        }
    }
    eka.push_back(n);

    vector<int> cnt(eka.size() - 1);
    for(int qi = 0; qi < q; ++qi) {
        int a, b;
        cin >> a >> b;
        --a;
        for(int i = 0; i < (int)cnt.size(); ++i) {
            int x = std::clamp(eka[i], a, b);
            int y = std::clamp(eka[i + 1], a, b);
            cnt[i] = y - x;
        }

        int A = 0;
        int B = (b - a) / 2;
        while(A != B) {
            int M = (A + B + 1) / 2;
            bool ok = true;
            int av = 0;
            int ac = cnt[av];
            int bv = (int)cnt.size() - 1;
            int i = M;
            int bc = 0;
            while(i > 0) {
                if(i == cnt[bv]) {
                    bc = cnt[bv];
                    i = 0;
                } else if(i < cnt[bv]) {
                    bc = i;
                    i = 0;
                } else {
                    i -= cnt[bv];
                    --bv;
                }
            }
            if(i != 0) {
                throw 5;
            }
            while(i < M) {
                while(ac == 0) {
                    ++av;
                    ac = cnt[av];
                }
                while(bc == 0) {
                    ++bv;
                    bc = cnt[bv];
                }
                if(bv < 2 * av) {
                    ok = false;
                    break;
                }
                int c = min(ac, bc);
                i += c;
                ac -= c;
                bc -= c;
            }
            if(ok) {
                A = M;
            } else {
                B = M - 1;
            }
        }
        cout << A << "\n";
    }

    return 0;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: RUNTIME ERROR

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED