Submission #1283083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283083		LmaoLmao	Index (COCI21_index)	C++20	110 / 110	805 ms	100524 KiB

index

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa = array<int,4>;
const int N=2e5+5;
const int MOD=1e9+7;

struct PSMT {
    int S[N*25],L[N*25],R[N*25];
    int timer=0;
    vector<int> root;
    int create(int val,int l,int r) {
        S[++timer]=val;
        L[timer]=l;
        R[timer]=r;
        return timer;
    }

    int build(int l,int r) {
        if(l==r) {
            return create(0,0,0);
        }
        int mid = l + r >> 1;
        return create(0,build(l,mid),build(mid+1,r));
    }

    void setup() {
        root.push_back(0);
        build(1,N-5);
    }
    int upd(int id,int l,int r,int pos,int val) {
        if(pos < l || r < pos) return id;
        if(l==r) {
            return create(S[id]+val,0,0);
        }
        int mid = l + r >> 1;
        int left=upd(L[id],l,mid,pos,val);
        int right=upd(R[id],mid+1,r,pos,val);
        return create(S[left]+S[right],left,right);
    }
    int GET(int id,int l,int r,int u,int v){
        if(v < l || r < u) return 0;
        if(u<=l && r<=v) {
            return S[id];
        }
        int mid = l + r >> 1;
        int left=GET(L[id],l,mid,u,v);
        int right=GET(R[id],mid+1,r,u,v);
        return left+right;
    }
    void update(int pos,int val) {
        root.push_back(upd(root.back(),1,N-5,pos,val));
    }
    int get(int u,int l,int r) {
        return GET(root[u],1,N-5,l,r);
    }
} SMT;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,q;
    cin >> n >> q;
    SMT.setup();
    for(int i=1;i<=n;i++) {
        int x;
        cin >> x;
        SMT.update(x,1);
    }
    while(q--) {
        int x,y;
        cin >> x >> y;
        int l=1,r=n;
        int ans=0;
        while(l<=r) {
            int mid = l + r >> 1;
            if(SMT.get(y,mid,n)-SMT.get(x-1,mid,n)>=mid) {
                l=mid+1;
                ans=mid;
            }
            else {
                r=mid-1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

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