Submission #638645

#	Time	Username	Problem	Language	Result	Execution time	Memory
638645		HaYoungJoon	Index (COCI21_index)	C++14	110 / 110	1758 ms	54684 KiB

index

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2e5 + 1;

struct Node {
    int val,Lid,Rid;
    Node() {};
    Node(int val, int L, int R): val(val), Lid(L), Rid(R) {}
} t[21*maxn];

int n,Q, root[maxn + 1], nNode = 0, version = 0;

int build(int tl, int tr) {
    int cur = ++nNode;
    if (tl == tr) t[cur] = Node(0,0,0);
    else {
        int tm = (tl + tr)/2;
        t[cur].val = 0;
        t[cur].Lid = build(tl,tm);
        t[cur].Rid = build(tm+1,tr);
    }
    return cur;
}
int update(int oldID, int tl, int tr, int pos) {
    if (tl == tr) {
        ++nNode;
        t[nNode] = Node(t[oldID].val + 1,0,0);
        return nNode;
    }
    int tm = (tl + tr)/2;
    int cur = ++nNode;
 //   assert(cur < 11*maxn);
    if (pos <= tm) {
        t[cur].Lid = update(t[oldID].Lid,tl,tm,pos);
        t[cur].Rid = t[oldID].Rid;
        t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
    } else {
        t[cur].Rid = update(t[oldID].Rid,tm+1,tr,pos);
        t[cur].Lid = t[oldID].Lid;
        t[cur].val = t[t[cur].Lid].val + t[t[cur].Rid].val;
    }
    return cur;
}

int get(int cur, int tl, int tr, int l, int r) {
    if (tl > r || tr < l) return 0;
    if (tl >= l && tr <= r) return t[cur].val;
    int tm = (tl + tr)/2;
    return get(t[cur].Lid,tl,tm,l,r) + get(t[cur].Rid,tm+1,tr,l,r);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> Q;
    root[0] = build(1,maxn - 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        ++version;
        root[version] = update(root[version-1],1,maxn-1,x);
    }
 //   cout << nNode << '\n';
    while (Q--) {
        int l,r;
        cin >> l >> r;
        int res = 0, L = 1, R = r - l + 1;
        while (L <= R) {
            int mid = (L + R)/2;
            if (get(root[r],1,maxn-1,mid,maxn-1) - get(root[l-1],1,maxn-1,mid,maxn-1) >= mid) {
                res = mid;
                L = mid+1;
            } else R = mid-1;
        }
        printf("%d\n",res);
    }
    return 0;
}

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