Submission #1154420

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154420		WongYiKai	Index (COCI21_index)	C++20	0 / 110	290 ms	589824 KiB

index

#pragma GCC optimize("O3")

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

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}

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

void build(int a[], int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = vector<int>(1, a[tl]);
    } else { 
        int tm = (tl + tr) / 2;
        build(a, v*2, tl, tm);
        build(a, 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 > r)
        return INF;
    if (l == tl && r == tr) {
        vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
        if (pos != t[v].end())
            return *pos;
        return INF;
    }
    int tm = (tl + tr) / 2;
    return min(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;
	n = readInt();
	q = readInt();
	int p[n+5];
	for (int i=0;i<n;i++){
		ll temp;
		temp = readInt();
		p[i] = temp;
	}

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

}

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