Submission #485710

#	Time	Username	Problem	Language	Result	Execution time	Memory
485710		KazamaHoang	Index (COCI21_index)	C++14	110 / 110	596 ms	8584 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int B = 500;

struct FenwickTree {
    int n;
    vector<int> tree;

    FenwickTree(int _n) {
        n = _n;
        tree.resize(n+5, 0);
    }

    void update(int x) {
        for (; x <= n; x += x & -x)
            tree[x] ++;
    }

    int get(int x) {
        int res = 0;
        for (; x; x -= x & -x)
            res += tree[x];
        return res;
    }
};

int n, q;
pair<int, int> a[200005];
int l[200005], r[200005];
int lo[200005], hi[200005];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i].first;
        a[i].second = i;
    }
    for (int i = 1; i <= q; ++ i) {
        cin >> l[i] >> r[i];
        lo[i] = 0, hi[i] = n + 1;
    }
    sort(a + 1, a + 1 + n);
    int rem = q;
    for (;;) {
        vector<pair<int, int>> mid(rem);
        for (int i = 1, cnt = 0; i <= q; ++ i)
            if (hi[i] - lo[i] > 1) {
                int cur = (lo[i] + hi[i]) >> 1;
                mid[cnt++] = {cur, i};
            }
        sort(mid.begin(), mid.end());
        reverse(mid.begin(), mid.end());
        FenwickTree ft(n);
        int run = n;
        for (auto& pii : mid) {
            while (run >= 1 && a[run].first >= pii.first) {
                ft.update(a[run].second);
                -- run;
            }
            int u = pii.second;
            int cur = ft.get(r[u]) - ft.get(l[u]-1);
            if (cur >= pii.first)
                lo[u] = pii.first;
            else
                hi[u] = pii.first; 
            if (hi[u] - lo[u] == 1) -- rem;
        }
        if (rem == 0) break;
    }
    for (int i = 1; i <= q; ++ i)
        cout << lo[i] << "\n";
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 40 / 40
• Subtask 3: 50 / 50