Submission #403220

#	Time	Username	Problem	Language	Result	Execution time	Memory
403220		MohamedAhmed04	Index (COCI21_index)	C++14	110 / 110	846 ms	19440 KiB

index

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] , L[MAX] , R[MAX] ;
int n , q ;
int cnt[MAX] , ans[MAX] ;

vector< pair<int , int> >vp(MAX) ;
vector<int>queries[MAX] ;

int bit[MAX] ;

void add(int i , int val)
{
	for(; i < MAX ; i += (i & (-i)))
		bit[i] += val ;
}

int get(int i)
{
	int sum = 0 ;
	for(; i > 0 ; i -= (i & (-i)))
		sum += bit[i] ;
	return sum ;
}

int query(int l , int r)
{
	return (get(r) - get(l - 1)) ; 
}

void init()
{
	for(int i = 1 ; i <= n ; ++i)
		queries[i].clear() ;
	memset(bit , 0 , sizeof(bit)) ;
	memset(cnt , 0 , sizeof(cnt)) ; 
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>q ;
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	for(int i = 1 ; i <= q ; ++i)
	{
		cin>>L[i]>>R[i] ;
		vp[i] = {1 , n} ;
	}
	bool ok = false ;
	while(!ok)
	{
		ok = true ;
		init() ;
		for(int i = 1 ; i <= q ; ++i)
		{
			if(vp[i].first > vp[i].second)
				continue ;
			ok = false ;
			queries[L[i]-1].push_back(-i) ;
			queries[R[i]].push_back(i) ;
		}
		for(int i = 1 ; i <= n ; ++i)
		{
			add(arr[i] , 1) ;
			for(auto &j : queries[i])
			{
				int sgn = 1 ;
				if(j < 0)
					j *= -1 , sgn = -1 ;
				cnt[j] += sgn * query((vp[j].first + vp[j].second) >> 1 , MAX-1) ;
			}
		}
		for(int i = 1 ; i <= q ; ++i)
		{
			if(vp[i].first > vp[i].second)
				continue ;
			int x = (vp[i].first + vp[i].second) >> 1 ;
			if(cnt[i] >= x)
				ans[i] = x , vp[i].first = x+1 ;
			else
				vp[i].second = x-1 ;
		}
	}
	for(int i = 1 ; i <= q ; ++i)
		cout<<ans[i]<<"\n" ;
	return 0 ;
}		

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