Kyselyt

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define D(x) {x;}
#else
#define D(x)
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin.exceptions(cin.failbit);
    int n, q;
    cin >> n >> q;
    int st[n+1][102] {};
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        st[i][x]++;
    }

    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k <= 100; ++k) st[i][k] += st[i-1][k];
    }

    for (int qi = 0; qi < q; ++qi) {
        int a, b;
        cin >> a >> b;
        a--;
        auto v = [&](int k) {
            return st[b][k] - st[a][k];
        };
        int tot = b-a;
        int lo = 0, hi = tot/2+1;
        while (hi-lo > 1) {
            int md = (lo+hi)/2;
            int hs = 0;
            int hp = 100;
            for (; hp > 0; --hp) {
                hs += v(hp);
                if (hs >= md) break;
            }
            int ht = hs-md;
            int ls = 0, lt = 0;
            bool f = 1;
            D(cout << "START " << md << endl);
            for (int lp = 1; lp <= 100; ++lp) {
                D(cout << "lp " << lp << " hp " << hp << endl);
                lt = 0;
                while (ls < md && lt < v(lp)) {
                    if (hp > 100 || 2*lp > hp) {
                        f = 0; break;
                    }
                    int tk = min(v(lp)-lt, v(hp)-ht);
                    D(cout << "tk " << tk << endl);
                    ls += tk;
                    lt += tk;
                    ht += tk;
                    while (hp < 100 && ht == v(hp)) hp++, ht = 0;
                }
                if (!f) break;
            }
            if (f) lo = md;
            else hi = md;
        }
        cout << lo << "\n";
        // int xa = 1, ta = 0;
        // while (xa <= 100 && !v(xa)) xa++;
        // if (xa == 101) {
        //     cout << 0 << "\n";
        //     continue;
        // }
        // int xb = 2*xa, tb = 0;
        // while (xb <= 100 && !v(xb)) xb++;
        // int xc = xb, tc = 0;
        // int res = 0;
        // while (xc <= 100) {
        //     int tk = min(v(xa)-ta, v(xc)-tc);
        //     if (xa == xb) tk = min(tk, tb-ta);
        //     res += tk;
        //     ta += tk;
        //     tc += tk;
        //     if (ta == v(xa)) {
        //         ta = 0;
        //         xa++;
        //         while (xa <= 
        //     }
        // }
    }
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: RUNTIME ERROR

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED