Submission #1264537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264537		niu_zh	OGLEDALA (COI15_ogledala)	C++17	19 / 100	4091 ms	5652 KiB

ogledala

/*
 * @FilePath: tmp.cpp
 * @Author: niu-zh
 */
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
pair<int,int> seqleft(int l,int r)
{
	int len=r-l+1;
	if(len%2)
	{
		return {l,l+(len-1)/2-1};
	}
	else
	{
		return {l,l+len/2-2};
	}
}
pair<int,int> seqright(int l,int r)
{
	int len=r-l+1;
	if(len%2)
	{
		return {l+(len+1)/2,r};
	}
	else
	{
		return {l+len/2,r};
	}
}
int a[N];
map<int,int> mp;
unordered_map<int,vector<pair<int,int>>> change;
int nowidx;
void dfs(int l,int r)
{
	if(r<l)
	{
		return;
	}
	int len=r-l+1;
	mp[len]++;
	if(change[len].empty()||change[len].back().first!=nowidx)
	{
		change[len].push_back({nowidx,1});
	}
	else
	{
		change[len].back().second++;
	}
	auto [ll,rl]=seqleft(l,r);
	auto [lr,rr]=seqright(l,r);
	dfs(ll,rl);
	dfs(lr,rr);
}
int cnt[N],to[N],la,ra;
int solve(int l,int r,int len,int pos)
{
	if(r<l)
	{
		return 0;
	}
	if(r-l+1<len)
	{
		return 0;
	}
	if(r-l+1==len)
	{
		if(pos==1)
		{
			la=l;
			ra=r;
			return -1;
		}
		return 1;
	}
	auto [ll,rl]=seqleft(l,r);
	int ls=solve(ll,rl,len,pos);
	if(ls==-1)
	{
		return -1;
	}
	auto [lr,rr]=seqright(l,r);
	int rs=solve(lr,rr,len,pos-ls);
	if(rs==-1)
	{
		return -1;
	}
	return ls+rs;
}
signed main()
{
	int m,n,T;
	cin>>m>>n>>T;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	a[0]=0;
	a[n+1]=m+1;
	for(int i=1;i<=n+1;i++)
	{
		if(a[i]-a[i-1]-1>0)
		{
			nowidx=i;
			dfs(a[i-1]+1,a[i]-1);
		}
	}
	int cntn=0;
	for(auto [k,v]:mp)
	{
		cnt[++cntn]=v;
		to[cntn]=k;
		for(int i=1;i<change[k].size();i++)
		{
			change[k][i].second+=change[k][i-1].second;
		}
	}
	for(int i=cntn;i>=1;i--)
	{
		cnt[i]+=cnt[i+1];
	}
	while(T--)
	{
		int x;
		cin>>x;
		if(x<=n)
		{
			cout<<a[x]<<'\n';
			continue;
		}
		x-=n;
		int l=1,r=cntn,leni=-1;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(cnt[mid]>=x)
			{
				leni=mid;
				l=mid+1;
			}
			else
			{
				r=mid-1;
			}
		}
		int pos=x;
		if(leni<cntn)
		{
			pos-=cnt[leni+1];
		}
		int len=to[leni];
		l=0,r=change[len].size()-1;
		int ans=0;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(change[len][mid].second>=pos)
			{
				ans=mid;
				r=mid-1;
			}
			else
			{
				l=mid+1;
			}
		}
		if(ans>0)
		{
			pos-=change[len][ans-1].second;
		}
		la=0;
		ra=0;
		solve(a[change[len][ans].first-1]+1,a[change[len][ans].first]-1,len,pos);
		if((ra-la+1)%2)
		{
			cout<<la+(ra-la+2)/2-1<<'\n';
		}
		else
		{
			cout<<la+(ra-la+1)/2-1<<'\n';
		}
	}
	return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59