Submission #447904

#	Time	Username	Problem	Language	Result	Execution time	Memory
447904		Jasiekstrz	Index (COCI21_index)	C++17	110 / 110	814 ms	11204 KiB

index

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=2e5;
int tab[N+10];
int srt[N+10];
int l[N+10],r[N+10];
int bg[N+10],en[N+10];
int fen[N+10];
int lsb(int x) { return x&(-x); }
void add(int x,int n)
{
	for(;x<=n;x+=lsb(x))
		fen[x]++;
	return;
}
int read(int x)
{
	int ans=0;
	for(;x>0;x-=lsb(x))
		ans+=fen[x];
	return ans;
}
int read(int ll,int rr)
{
	return read(rr)-read(ll-1);
}
void bs(int n,int q)
{
	int active=q;
	vector<pair<int,int>> mid;
	while(active>0)
	{
		for(int i=1;i<=n;i++)
		{
			if(bg[i]<en[i])
				mid.emplace_back((bg[i]+en[i]+1)/2,i);
		}
		sort(mid.begin(),mid.end());
		for(int i=0;i<=n;i++)
			fen[i]=0;
		for(int i=1;i<=n;i++)
		{
			while(!mid.empty() && mid.back().fi>tab[srt[i]])
			{
				auto [m,x]=mid.back();
				mid.pop_back();
				if(read(l[x],r[x])>=m)
					bg[x]=m;
				else
					en[x]=m-1;
				if(bg[x]>=en[x])
					active--;
			}
			add(srt[i],n);
		}
		while(!mid.empty())
		{
			auto [m,x]=mid.back();
			mid.pop_back();
			bg[x]=m;
			if(bg[x]>=en[x])
				active--;
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i];
		srt[i]=i;
	}
	sort(srt+1,srt+n+1,[](int a,int b){ return tab[a]>tab[b]; });
	for(int i=1;i<=q;i++)
	{
		cin>>l[i]>>r[i];
		bg[i]=0;
		en[i]=n;
	}
	bs(n,q);
	for(int i=1;i<=q;i++)
		cout<<bg[i]<<"\n";
	return 0;
}

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