Submission #485707

#	Time	Username	Problem	Language	Result	Execution time	Memory
485707		KazamaHoang	Index (COCI21_index)	C++14	110 / 110	829 ms	9924 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int B = 500;

struct FenwickTree {
    vector<int> tree;

    FenwickTree() {
        tree.resize((int)2e5 + 5, 0);
    }

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

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

int n, q;
int a[200005];
int l[200005], r[200005], id[200005], ans[200005];
FenwickTree ft;

bool comp(int u, int v) {
    if (l[u] / B != l[v] / B)
        return l[u] / B < l[v] / B;
    return r[u] < r[v];
}

void add(int u, int sign) {
    ft.update(a[u], sign);    
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; ++ i)
        cin >> a[i];
    for (int i = 1; i <= q; ++ i) {
        cin >> l[i] >> r[i];
        id[i] = i;
    }
    sort(id + 1, id + 1 + q, comp);
    for (int i = 1, curL = 2, curR = 1; i <= q; ++ i) {
        int u = id[i];
        while (curL > l[u]) add(-- curL, 1);
        while (curL < l[u]) add(curL ++, -1);
        while (curR < r[u]) add(++ curR, 1);
        while (curR > r[u]) add(curR --, -1);
        int lo = 0, hi = n + 1;
        while (hi - lo > 1) {
            int mid = (hi + lo) >> 1;
            if (ft.get(mid) >= mid) 
                lo = mid;
            else 
                hi = mid;
        }
        ans[u] = lo;
    }
    for (int i = 1; i <= q; ++ i) 
        cout << ans[i] << "\n";
    return 0;
}

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