Submission #1047316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047316		vjudge1	Index (COCI21_index)	C++14	110 / 110	2261 ms	56788 KiB

index

#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define fi first
#define se second
#define sp " "
#define pb push_back
typedef int lo;

const int inf = 1e9+7;
vector<lo> mt[4*MAXN];
int n,k,q;
int arr[MAXN];
inline void build(int node, int start, int end)
{
	if(start == end)
	{
		mt[node].pb(arr[start]);
		return;
	}
	int mid = (start+end)/2;
	build(node*2,start,mid);
	build(node*2+1,mid+1,end);
	mt[node].resize(mt[node*2].size()+mt[node*2+1].size());
	merge(mt[node*2].begin(),mt[node*2].end(),mt[node*2+1].begin(),mt[node*2+1].end(),mt[node].begin());

	
}

inline int query(int node, int start, int end,int l,int r,int val)
{
	if(start > end or start > r or end < l)
	{
		return 0;
	}
	if(start >= l and end <= r)
	{
		int a = lower_bound(mt[node].begin(),mt[node].end(),val) - mt[node].begin();
		return mt[node].size()-a;
	}
	int mid = (start+end)/2;
	return query(node*2,start,mid,l,r,val) + query(node*2+1,mid+1,end,l,r,val);
}


int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> n >> q;;
	for (int i = 1; i <= n; ++i)
	{
		cin >> arr[i];
	}
	build(1,1,n);
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		lo bas = 0;
		lo son = 1000000;
		while(bas <= son)
		{
			lo mid = (bas+son)/2;
			//~ cout << mid << sp << query(1,1,n,l,r,mid) << endl;
			if(query(1,1,n,l,r,mid) >= mid)
			{
				bas = mid+1;
			}
			else
			{
				son = mid-1;
			}
			
		}
		cout << son << endl;
	}
	
}

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