Submission #1215030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215030		zfs732	OGLEDALA (COI15_ogledala)	C++20	100 / 100	1562 ms	10632 KiB

ogledala

//蒟蒻一枚 rp++
//即得易见平凡，仿照上例显然。留作习题答案略，读者自证不难
//反之亦然同理，推论自然成立，略去过程Q.E.D.，由上可知证毕
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define re register
#define il inline
#define gc() getchar()
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define repp(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define tep(i,x) for(int i=head[x];~i;i=ne[i])
#define ls(x) x<<1
#define rs(x) x<<1|1
#define epos (1e-9)
#define inf 0x3f3f3f3f
#define INF 1e16
#define pii pair<int,int>
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define fi first
#define sc second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef double db;
namespace IO{
//	#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<9,stdin),p1==p2)?EOF:*p1++)
//	char buf[1<<9],*p1=buf,*p2=buf;
	template<typename T> inline void read(T &x){
		bool f=1;x=0;char ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')f=0;ch=gc();}
		while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=gc();
		x=f?x:-x;
	}
	template<typename T> inline void write(T x){
		if(x<0) putchar('-'),x=-x;
	   	if(x>9) write(x/10);
	   	putchar(char('0'+x%10));
	}
	template <typename T,typename ...Args> inline
	void read(T &x,Args &...args){read(x);read(args...);}
	template<typename T> inline void write(T x,char c){write(x),putchar(c);}
}
using namespace IO;
namespace MOD{
	typedef uint32_t u32;
	typedef uint64_t u64;
	typedef __uint128_t u128;
	u64 p,m;
	void set_mod(u32 mod){
		m=mod,p=-m/m+1;
	}
	u64 mo(u64 x){//取模优化
		x-=u64((u128)x*p>>64)*m;
		return (x>=m)?x-m:x;
	}
}
bool _ST;
#define int LL
const int N=1e5+100;
struct NODE{
    int len,pos,cnt1,cnt2,ori,type;
    NODE(int _len=0,int _pos=0,int _cnt1=0,int _cnt2=0,int _ori=0,int _type=0){
        len=_len,pos=_pos,cnt1=_cnt1,cnt2=_cnt2,ori=_ori,type=_type;
    }
    bool operator <(const NODE&T)const{
        return (len==T.len)?pos>T.pos:len<T.len;
    }
};
int n,q;
LL m,pos[N],a[N],ans[N];
priority_queue<NODE> que;
pii qu[N];
LL calc1(LL len,LL k,LL t){
    LL res=0;
    while(len>1){
        if(t<=(k>>1)) len>>=1,k>>=1;
        else res+=len>>1,len>>=1,t-=(k>>1),k=(k+1)>>1;
    }
    return res+1;
}
LL calc2(LL len,LL k,LL t){
    LL res=0;
    while(len>1){
        if(t<=len/2-(k>>1)) len>>=1,k>>=1;
        else res+=len>>1,t-=len/2-(k>>1),len>>=1,k=(k+1)>>1;
    }
    return res+1;
}
LL calc3(LL len,LL k,LL t){
    LL res=0;
    while(len>1){
        if(t<=len/2) len>>=1,k>>=1;
        else res+=k>>1,t-=len/2,len>>=1,k=(k+1)>>1;
    }
    return res+k;
}
bool _ED;
signed main(){
	fprintf(stderr,"%.20lf MB\n",(&_ST-&_ED)/1048576.0);
	//ios::sync_with_stdio(false);
	//cin.tie(0);cout.tie(0);

    read(m,n,q);
    rep(i,1,n) read(a[i]),pos[i]=a[i];
    sort(a+1,a+1+n);a[n+1]=m+1;
    rep(i,1,n+1) if(a[i]-a[i-1]-1>0) que.push(NODE(a[i]-a[i-1]-1,a[i-1]+1,1,0,1,0));

    rep(i,1,q) read(qu[i].fi),qu[i].sc=i;
    sort(qu+1,qu+q+1);

    int cur=1;
    while(cur<=q&&qu[cur].fi<=n) ans[qu[cur].sc]=pos[qu[cur].fi],++cur;

    LL ti=n;
    while(!que.empty()&&cur<=q){
        auto u=que.top();que.pop();
        if(!u.len) break;
        LL ed=ti+u.cnt1;
        //cerr<<ti<<" "<<ed<<endl;
        if(u.type==2) ed+=u.cnt2;

        while(cur<=q&&qu[cur].fi<=ed){
            if(u.type==0){
                LL res=calc1(u.ori,u.cnt1,qu[cur].fi-ti);
                ans[qu[cur].sc]=u.pos+(qu[cur].fi-ti-1)*(u.len+1)+(res-(qu[cur].fi-ti))*u.len+(u.len-1)/2;
            }
            else if(u.type==1){
                LL res=calc2(u.ori,u.cnt2,qu[cur].fi-ti);
                ans[qu[cur].sc]=u.pos+(qu[cur].fi-ti-1)*(u.len+1)+(res-(qu[cur].fi-ti))*(u.len+2)+(u.len-1)/2;
            }
            else{//1
                LL res=calc3(u.ori,u.cnt1,qu[cur].fi-ti);
                ans[qu[cur].sc]=u.pos+2ll*(qu[cur].fi-ti-1)+res;
            }
            ++cur;
        }

        ti=ed;

        if(u.type==0){
            if(u.len==2){

                que.push(NODE(1,u.pos,u.cnt1,u.cnt2,u.ori,2));
            }
            else{
                que.push(NODE(u.len-1,u.pos,u.cnt2,u.cnt1,u.ori,1));
            }
        }
        if(u.type==1){
            int cnt1,cnt2;
            if(u.len%2==0) cnt1=u.cnt1+u.cnt2*2,cnt2=u.cnt1;//0->00,1->01
            else cnt1=u.cnt2,cnt2=u.cnt1*2+u.cnt2;
            que.push(NODE((u.len+1)/2,u.pos,cnt1,cnt2,u.ori*2ll,0));
        }
    }
    rep(i,1,q) write(ans[i],'\n');
	fprintf(stderr,"%.4lf s\n",1.0*clock()/CLOCKS_PER_SEC);
	return 0;
}
// ./seat < seat3.in > seat.out
//谨记:
//十年OI一场空，不开longlong见祖宗
//数据千万条，清空第一条。多测不清空，爆零两行泪。清空不规范，TLE总相伴。
//快读要加类型名

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