Submission #1306208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306208		AMnu	Index (COCI21_index)	C++20	110 / 110	886 ms	59596 KiB

index

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;

const int MAXN = 2e5+5, SEG = MAXN*22, MAXP = 2e5;

int N, Q, X, Y, cnt, val[SEG], lef[SEG], rig[SEG], ver[MAXN];
vector <int> P[MAXN];

int build(int L,int R) {
    int x = cnt;
    cnt++;
    if (L == R) {
        val[x] = 0;
    }
    else {
        int mid=(L+R)/2;
        lef[x] = build(L,mid);
        rig[x] = build(mid+1,R);
        val[x] = val[lef[x]] + val[rig[x]];
    }
    return x;
}

int query(int tr,int x,int y,int L,int R) {
    if (x <= L && y >= R) {
        return val[tr];
    }
    if (x > R || y < L) {
        return 0;
    }
    int mid = (L+R)/2;
    return query(lef[tr],x,y,L,mid) + query(rig[tr],x,y,mid+1,R);
}

int update(int tr,int x,int y,int L,int R) { // arr[x] = y;
    int c = cnt;
    cnt++;
    if (L == R) {
        val[c] = y;
    }
    else {
        int mid = (L+R)/2;
        if (x <= mid) {
            lef[c] = update(lef[tr],x,y,L,mid);
            rig[c] = rig[tr];
        }
        else {
            lef[c] = lef[tr];
            rig[c] = update(rig[tr],x,y,mid+1,R);
        }
        val[c] = val[lef[c]] + val[rig[c]];
    }
    return c;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> Q;
    for (int i=1;i<=N;i++) {
        cin >> X;
        P[X].push_back(i);
    }
    ver[MAXP] = build(1,N);
    for (int i=MAXP;i>1;i--) {
        for (int x : P[i]) {
            ver[i] = update(ver[i],x,1,1,N);
        }
        ver[i-1] = ver[i];
    }
    while (Q--) {
        cin >> X >> Y;
        int L = 2, R = MAXP, ans = 1;
        while (L <= R) {
            int mid = (L+R)/2;
            if (query(ver[mid],X,Y,1,N) >= mid) {
                ans = mid;
                L = mid+1;
            }
            else {
                R = mid-1;
            }
        }
        cout << ans << "\n";
    }
}

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