Submission #1154441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154441		WongYiKai	Index (COCI21_index)	C++20	0 / 110	13 ms	19264 KiB

index

#include <bits/stdc++.h>
using namespace std;
typedef int ll;

const ll MAXN = 200005;
 
vector<int> t[4*MAXN];
int a[MAXN];

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = {a[tl]};
        return;
    }
    int tm = (tl + tr) / 2;
    build(v*2, tl, tm);
    build(v*2+1, tm+1, tr);
    merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
          back_inserter(t[v]));
    
}

int query(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || tl > r)
        return 0;
    if (l == tl && r == tr) {
        return t[v].end() - lower_bound(t[v].begin(), t[v].end(), x);
    }
    int tm = (tl + tr) / 2;
    return (query(v*2, tl, tm, l, min(r, tm), x)+
               query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n,q;
	cin >> n >> q;
	for (int i=1;i<=n;i++){
		cin >> a[i];
	}

	build(1, 1, n);
	
	
	while (q--){
		ll l,r;
		cin >> l >> r;
		ll range = r-l+1;
		ll l2=1,r2=range;
		while (l2<r2){
			ll m = l2+(r2-l2)/2;
			if (r2-l2==1) m=r2;
			if(query(1, 0,n-1, l, r, m) >= m) l2=m;
			else r2=m-1;
		}
		cout << l2 << "\n";
	}
    
}

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