Submission #1215056

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215056		dyj133446	OGLEDALA (COI15_ogledala)	C++20	100 / 100	1156 ms	258232 KiB

ogledala

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+5;
ll m,n,q,a[N],ans[N],p1[N][50],p2[N][50],p3[N][50],tot;
pair<ll,int>b[N];
struct node{
	ll val;
	int id,op,op1;
}A[100*N];
bool pdB()
{
	a[n+1]=m+1;
	for(int i=1;i<=n+1;i++)
	{
		ll x=a[i]-a[i-1]-1;
		if((1ll<<__lg(x+1))!=x+1)return false;
	}
	return true;
}
bool cmp(node s,node t)
{
	if(s.val==t.val)return s.id<t.id;
	return s.val>t.val;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>m>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=q;i++)cin>>b[i].first,b[i].second=i;
	sort(b+1,b+q+1);
	int l=1;
	while(l<=q&&b[l].first<=n)ans[b[l].second]=a[b[l].first],l++;
	sort(a+1,a+n+1),a[n+1]=m+1;
	for(int i=1;i<=n+1;i++)if(a[i]!=a[i-1]+1)
	{
		ll c1=1,c2=0,t=a[i]-a[i-1]-1,s=0,k=0;
		p1[i][0]=c1,p2[i][0]=c2,p3[i][0]=t;
		while(t)
		{
			if(t==1)break;
			s+=c1+(t!=2)*c2;
			ll t1=0,t2=0;
			if(t&1)t1=2*c1+c2,t2=c2;
			else t1=c1,t2=2*c2+c1;
			if(t==2)t1+=c2,p2[i][k]=0;
			t/=2,c1=t1,c2=t2,k++;
			p1[i][k]=c1,p2[i][k]=c2,p3[i][k]=t;
		}
		for(int j=0;j<=k;j++)
		{
			if(p1[i][j])A[++tot]=(node){p3[i][j],i,j,0};
			if(p2[i][j])A[++tot]=(node){p3[i][j]-1,i,j,-1};
		}
	}
	sort(A+1,A+tot+1,cmp);
	ll s=n;
	for(int i=1;i<=tot;i++)
	{
		ll v=p1[A[i].id][A[i].op];
		if(A[i].op1)v=p2[A[i].id][A[i].op];
		while(l<=q&&b[l].first<=s+v)
		{
			if(p3[A[i].id][A[i].op]-A[i].op1==1)
			{
				ll t1=b[l].first-s,len=a[A[i].id]-a[A[i].id-1]-1,res=0,C=v;
				while(len!=1)
				{
					ll lef=(len-1)/2,t=C/2;
					if(t<t1)t1-=t,res+=lef+1,len/=2,C-=t;
					else len=(len-1)/2,C=t;
				}
				ans[b[l].second]=res+1+a[A[i].id-1];
				l++;
				continue;
			}
			ll rk=b[l].first-s,rk1=0,res=0,q1=v;
			if(!A[i].op1)
			{
				for(int x=0;x<A[i].op;x++)
				{
					int op=1;
					if(rk-q1/2>0)rk-=q1/2,op=0,q1=(q1+1)/2;
					else q1=q1/2;
					if(!op)
					{
						if(rk1+(1ll<<x)<p1[A[i].id][x+1])res+=p3[A[i].id][x+1]+1;
						else res+=p3[A[i].id][x+1]; 
					}
					else rk1+=1ll<<x;
				}	
			}
			else{
				for(int x=0;x<A[i].op;x++)
				{
					int op=1;
					if(rk-(q1+1)/2>0)rk-=(q1+1)/2,op=0,q1=q1/2;
					else q1=(q1+1)/2;
					if(!op)
					{
						if(rk1+(1ll<<x)<p1[A[i].id][x+1])res+=p3[A[i].id][x+1]+1;
						else res+=p3[A[i].id][x+1];
					}
					else rk1+=1ll<<x;
				}
			}
			ans[b[l].second]=res+(A[i].val-1)/2+1+a[A[i].id-1];
			l++;
		}
		s+=v;
	}
	for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
	return 0;
}

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