QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#694504#6400. Game: Celestekkkgjyismine4WA 0ms18028kbC++202.1kb2024-10-31 18:05:422024-10-31 18:05:46

Judging History

This is the latest submission verdict.

  • [2024-10-31 18:05:46]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 18028kb
  • [2024-10-31 18:05:42]
  • Submitted

answer

#include<bits/stdc++.h>
#define N 1000005
#define ll long long
#define i28 __int128
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++
using namespace std;
static char buf[2999999], *p1 = buf, *p2 = buf;
template <typename item>
inline void read (register item &x) {
    x = 0;
	register char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
}
const ll mod=1e18+7,sd=1e6+7;
int n,l,r,a[N],b[N],lst[N],fl[N],rt[N],tot,son[22*N][2],ct[22*N];
ll hs[22*N],pw[N];
void Add(ll &x,const ll y){x=((x+y>=mod)?(x+y-mod):(x+y));}
#define mid (l+r>>1)
#define ls son[p][0]
#define rs son[p][1]
void ins(int &p,int q,int l,int r,int pos){
	p=++tot;son[p][0]=son[q][0],son[p][1]=son[q][1],hs[p]=hs[q],ct[p]=ct[q];
	Add(hs[p],pw[n-pos]),++ct[p];if(l==r)return;
    if(pos<=mid)ins(ls,son[q][0],l,mid,pos);else ins(rs,son[q][1],mid+1,r,pos);
}
int que[N],hd,tl;
bool cmp(int p,int q,int l,int r){
	if(hs[p]==hs[q])return 1;
	if(l==r)return (ct[p]>ct[q]);
	if(hs[son[p][1]]==hs[son[q][1]])return cmp(son[p][0],son[q][0],l,mid);
	return cmp(son[p][1],son[q][1],mid+1,r);
}
void solve(){
	read(n),read(l),read(r),pw[0]=1;
	for(int i=1;i<=n;++i)read(a[i]),pw[i]=(i28)pw[i-1]*(i28)sd%mod;
	for(int i=1;i<=n;++i)read(b[i]),fl[i]=rt[i]=lst[i]=0;
	for(int i=1;i<=tot;++i)son[i][0]=son[i][1]=ct[i]=hs[i]=0;tot=0;
	fl[1]=1,lst[1]=0,ins(rt[1],rt[1],1,n,b[1]);
	hd=1,tl=0;int Now=0;
	for(int i=2;i<=n;++i){
		while(Now+1<i&&a[i]-a[Now+1]>=l){
			++Now;if(!fl[Now])continue;
			while(hd<=tl&&cmp(rt[Now],rt[que[tl]],1,n))--tl;
			que[++tl]=Now;
		}
		while(hd<=tl&&a[i]-a[que[hd]]>r)++hd;
		if(hd<=tl)fl[i]=1,lst[i]=que[hd],rt[i]=rt[lst[i]],ins(rt[i],rt[i],1,n,b[i]);
		else fl[i]=0;
	}
	if(!fl[n])puts("-1");
	else{
		tl=0;
        for(int i=n;i;i=lst[i]){
        	if(lst[i])assert(a[i]-a[lst[i]]<=r&&a[i]-a[lst[i]]>=l);
			que[++tl]=b[i];
		}
        sort(que+1,que+tl+1);
        for(int i=tl;i>=1;--i)printf("%d ",que[i]);
        puts("");
	}
}
int main(){
	int T;read(T);
	while(T--)solve();
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 18028kb

input:

2
5 2 3
1 2 3 4 5
5 2 3 1 4
3 1 2
1 4 7
3 3 3

output:

5 4 3 
-1

result:

wrong answer 1st lines differ - expected: '3', found: '5 4 3 '