Submission #1154444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154444		WongYiKai	Index (COCI21_index)	C++20	60 / 110	2599 ms	102952 KiB

index

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

const int MAX = 2000005;
 
// Constructs a segment tree and stores sTree[]
void buildTree(int idx, int ss, int se, vector<ll> a[],
               vector<ll> sTree[])
{
    /*leaf node*/
    if (ss == se) {
        sTree[idx] = a[ss];
        return;
    }
 
    int mid = (ss + se) / 2;
 
    /* building left subtree */
    buildTree(2 * idx + 1, ss, mid, a, sTree);
 
    /* building right subtree */
    buildTree(2 * idx + 2, mid + 1, se, a, sTree);
 
    /* merging left and right child in sorted order */
    merge(sTree[2 * idx + 1].begin(),
          sTree[2 * idx + 1].end(),
          sTree[2 * idx + 2].begin(),
          sTree[2 * idx + 2].end(),
          back_inserter(sTree[idx]));
}
 
// Recursive function to count smaller elements from row
// a[ss] to a[se] and value smaller than or equal to k.
int queryRec(int node, int start, int end, int ss, int se,
             int k, vector<ll> a[], vector<ll> sTree[])
{
    /* If out of range return 0 */
    if (ss > end || start > se)
        return 0;
 
    /* if inside the range return count */
    if (ss <= start && se >= end) {
        /* binary search over the sorted vector
        to return count >= X */
        return upper_bound(sTree[node].begin(),
                           sTree[node].end(), k)
               - sTree[node].begin();
    }
 
    int mid = (start + end) / 2;
 
    /*searching in left subtree*/
    int p1 = queryRec(2 * node + 1, start, mid, ss, se, k,
                      a, sTree);
 
    /*searching in right subtree*/
    int p2 = queryRec(2 * node + 2, mid + 1, end, ss, se, k,
                      a, sTree);
 
    /*adding both the result*/
    return p1 + p2;
}
 
// A wrapper over query().
int query(int start, int end, int k, vector<ll> a[], int n,
          vector<ll> sTree[])
{
    return queryRec(0, 0, n - 1, start, end, k, a, sTree);
}


int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n,q;
	cin >> n >> q;
	vector<ll> p[n+5];
	for (int i=0;i<n;i++){
		ll temp;
		cin >> temp;
		p[i].push_back(temp);
	}

	vector<ll> sTree[MAX];
	buildTree(0,0,n-1,p,sTree);
	while (q--){
		ll l,r;
		cin >> l >> r;
		ll l2=0,r2=200005,m;
		while (l2<r2){
			m = l2+(r2-l2)/2;
			ll range = r-l+1;
			if(range - query(l-1,r-1,m-1,p,n,sTree) >= m) l2=m+1;
			else r2=m;
		}
		cout << l2-1 << "\n";
	}

}

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