Submission #1262845

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262845		niu_zh	OGLEDALA (COI15_ogledala)	C++17	0 / 100	4096 ms	4284 KiB

ogledala

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
using namespace std;
const int N=1e5+10;
map<int,int> cntm,to;
int cnt[N],a[N];
unordered_map<int,vector<pair<int,int>>> change;
int nowidx;
void dfs(int l,int r)
{
	if(l>r)
	{
		return;
	}
	int dis=r-l+1;
	cntm[dis]++;
	if(change[dis].empty()||change[dis].back().first!=nowidx)
	{
		change[dis].push_back({nowidx,1});
	}
	else
	{
		change[dis].back().second++;
	}
	if(dis%2)
	{
		dfs(l,l+(dis-1)/2-1);
		dfs(l+(dis+1)/2,r);
	}
	else
	{
		dfs(l,l+dis/2-2);
		dfs(l+dis/2,r);
	}
}
int la,ra;
int solve(int l,int r,int len,int pos)
{
	if(l>r)
	{
		return 0;
	}
	if(r-l+1==len)
	{
		if(pos==1)
		{
			la=l;
			ra=r;
			return -1;
		}
		else
		{
			return 1;
		}
	}
	int ls,rs;
	if((r-l+1)%2)
	{
		ls=solve(l,l+(r-l+1)/2-1,len,pos);
		if(ls==-1)
		{
			return -1;
		}
		rs=solve(l+(r-l+2)/2,r,len,pos-ls);
	}
	else
	{
		ls=solve(l,l+(r-l+1)/2-2,len,pos);
		if(ls==-1)
		{
			return -1;
		}
		rs=solve(l+(r-l+1)/2,r,len,pos-ls);
	}
	return ls+rs;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m,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=0;i<=n;i++)
	{
		if(a[i+1]-a[i]-1>0)
		{
			nowidx=i;
			dfs(a[i]+1,a[i+1]-1);
		}
	}
	int cntn=0;
	for(auto [k,v]:cntm)
	{
		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,alen;
		while(l<=r)
		{
			int mid=(l+r)>>1;
			if(cnt[mid]>=x)
			{
				alen=mid;
				l=mid+1;
			}
			else
			{
				r=mid-1;
			}
		}
		int pos=x;
		if(alen>0)
		{
			pos-=cnt[alen+1];
		}
		int len=to[alen];
		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;
			}
		}
		la=0;
		ra=0;
		if(ans==0)
		{
			solve(a[change[len][ans].first]+1,a[change[len][ans].first+1]-1,len,pos);
		}
		else
		{
			solve(a[change[len][ans].first]+1,a[change[len][ans].first+1]-1,len,pos-change[len][ans-1].second);
		}
		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: 0 / 19
• Subtask 2: 0 / 22
• Subtask 3: 0 / 59