QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#694504 | #6400. Game: Celeste | kkkgjyismine4 | WA | 0ms | 18028kb | C++20 | 2.1kb | 2024-10-31 18:05:42 | 2024-10-31 18:05:46 |
Judging History
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 '