QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194498#7522. Sequence Shiftucup-team1447#WA 2ms12240kbC++144.6kb2023-09-30 20:56:242023-09-30 20:56:25

Judging History

你现在查看的是最新测评结果

  • [2023-09-30 20:56:25]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:12240kb
  • [2023-09-30 20:56:24]
  • 提交

answer

// what is matter? never mind. 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2") 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define mod 1000000007
struct modint{
	int x;
	modint(int o=0){x=o;}
	modint &operator = (int o){return x=o,*this;}
	modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
	modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
	modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
	modint &operator ^=(int b){
		modint a=*this,c=1;
		for(;b;b>>=1,a*=a)if(b&1)c*=a;
		return x=c.x,*this;
	}
	modint &operator /=(modint o){return *this *=o^=mod-2;}
	friend modint operator +(modint a,modint b){return a+=b;}
	friend modint operator -(modint a,modint b){return a-=b;}
	friend modint operator *(modint a,modint b){return a*=b;}
	friend modint operator /(modint a,modint b){return a/=b;}
	friend modint operator ^(modint a,int b){return a^=b;}
	friend bool operator ==(modint a,int b){return a.x==b;}
	friend bool operator !=(modint a,int b){return a.x!=b;}
	bool operator ! () {return !x;}
	modint operator - () {return x?mod-x:0;}
	bool operator <(const modint&b)const{return x<b.x;}
};
inline modint qpow(modint x,int y){return x^y;}

vector<modint> fac,ifac,iv;
inline void initC(int n)
{
	if(iv.empty())fac=ifac=iv=vector<modint>(2,1);
	int m=iv.size(); ++n;
	if(m>=n)return;
	iv.resize(n),fac.resize(n),ifac.resize(n);
	For(i,m,n-1){
		iv[i]=iv[mod%i]*(mod-mod/i);
		fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*iv[i];
	}
}
inline modint C(int n,int m){
	if(m<0||n<m)return 0;
	return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
inline modint sign(int n){return (n&1)?(mod-1):(1);}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 4000505
#define inf 0x3f3f3f3f

int n,m,a[maxn],b[maxn],ida[maxn],ra[maxn],bb[maxn];
int lst,B=1800;

const double alp=1-sqrt(2)/2,delp=alp/(1-alp);
int sz[maxn],val[maxn],ls[maxn],rs[maxn],rt;
int rub[maxn],rtop,tot,rub2[maxn],rtop2;
int newn(){assert(tot<maxn-4);return rtop?rub[rtop--]:++tot;}
void thro(int u){rub2[++rtop2]=u;}
void clrs(){while(rtop2) rub[++rtop]=rub2[rtop2--];}
int newn(int v){
	int u=newn();
	sz[u]=1,val[u]=v,ls[u]=rs[u]=0; return u;
}

void up(int u){
	val[u]=val[rs[u]];
	sz[u]=sz[ls[u]]+sz[rs[u]];
}

void down(int u){
	
}
int up(int l,int r){
	int u=newn();
	return ls[u]=l,rs[u]=r,up(u),u;
}
int merge(int u,int v){
	if(!u||!v)return u|v;
	if(sz[u]>=delp*sz[v]&&sz[v]>=delp*sz[u])return up(u,v);
	if(sz[u]<=sz[v]){
		down(v),thro(v);
		int l=ls[v],r=rs[v];
		if(sz[r]>=alp*(sz[u]+sz[v]))return merge(merge(u,l),r);
		down(l),thro(l);
		return merge(merge(u,ls[l]),merge(rs[l],r));
	}else{
		down(u),thro(u);
		int l=ls[u],r=rs[u];
		if(sz[l]>=alp*(sz[u]+sz[v]))return merge(l,merge(r,v));
		down(r),thro(r);
		return merge(merge(l,ls[r]),merge(rs[r],v)); 
	}
}

void ins(int&p,int v){
	if(!ls[p]){
		if(mkp(b[val[p]],val[p])<mkp(b[v],v))p=merge(p,newn(v));
		else p=merge(newn(v),p);
		return;
	}
	if(mkp(b[v],v)<=mkp(b[val[ls[p]]],val[ls[p]]))ins(ls[p],v);
	else ins(rs[p],v);
	thro(p),p=merge(ls[p],rs[p]);
}
void del(int&p,int v){
	if(!ls[p])return p=0,void();
	if(mkp(b[v],v)<=mkp(b[val[ls[p]]],val[ls[p]]))del(ls[p],v);
	else del(rs[p],v);
	thro(p),p=merge(ls[p],rs[p]);
}

int res;
void work(int d)
{
	res=0;
	For(i,1,B){
		res=max(res,a[ida[i]]+b[ida[i]+d]);
	}
	function<void(int,int)>dfs=[&](int p,int ql){
		if(!ls[p]){
			res=max(res,b[val[p]]+a[val[p]-d]);
			return;
		}
		if(ql<=sz[ls[p]]) dfs(ls[p],ql);
		dfs(rs[p],ql-sz[ls[p]]);
	};
	dfs(rt,max(1,n-B));
	printf("%d\n",res);
}

signed main()
{
//	freopen("data.in","r",stdin);
//	freopen("my.out","w",stdout);
	n=read(),m=read();
	For(i,1,n)a[i]=read();
	For(i,1,n)b[i]=read(),ins(rt,i),clrs();
	For(i,1,n)ida[i]=i;
	sort(ida+1,ida+n+1,[&](int x,int y){
		return a[x]>a[y];
	});
	work(0);
	For(i,n+1,n+m){
		b[i]=read();
		b[i]^=res;
		ins(rt,i);
		del(rt,i-n);
		clrs();
	//	if(i%1000==0)cerr<<i<<"\n";
//		cout<<"tot "<<tot<<"\n";
		work(i-n);
	}
	return 0;
}
/*
5 3
1 4 3 2 5
7 5 8 3 2
3
6
4
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11956kb

input:

5 3
1 4 3 2 5
7 5 8 3 2
3
6
4

output:

11
13
16
25

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 11988kb

input:

1 0
103509429
823330096

output:

926839525

result:

ok single line: '926839525'

Test #3:

score: 0
Accepted
time: 2ms
memory: 12016kb

input:

1 1
576560149
691846236
1156187222

output:

1268406385
835582012

result:

ok 2 lines

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 12240kb

input:

1 10
700282491
332230980
90825676
1630266999
644973380
262379760
2122877054
1851957134
1370195232
110993724
1319359505
1883523208

output:

1032513471
1654684398
954401907
1213201842
1906957245
1206674754
1397518663
749038306
1408647769
1192430787
1628748486

result:

wrong answer 3rd lines differ - expected: '759763732', found: '954401907'