QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#518497 | #6400. Game: Celeste | louhao088 | WA | 0ms | 17924kb | C++23 | 2.3kb | 2024-08-13 21:06:52 | 2024-08-13 21:06:52 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5,base=19260817,mod=998244353;
#define mid (l+r>>1)
#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair
inline int read(){
char ch=getchar();int x=0;bool f=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1){x=-x;}return x;
}
int n,m,T,L,R;
int ls[maxn*30],rs[maxn*30],val[maxn*30],s[maxn*30];
int a[maxn],b[maxn],Rt[maxn],pw[maxn],tot=0;
deque<int>q;queue<int>q2;
void add(int &rt,int rt1,int l,int r,int pos){
rt=++tot;s[rt]=val[rt]=ls[rt]=rs[rt]=0;
if(l==r){val[rt]=(val[rt1]+pw[l])%mod;s[rt]=s[rt1]+1;return ;}
ls[rt]=ls[rt1],rs[rt]=rs[rt1];
if(mid>=pos)add(ls[rt],ls[rt1],l,mid,pos);
else add(rs[rt],rs[rt1],mid+1,r,pos);
val[rt]=(val[ls[rt]]+val[rs[rt]])%mod;
s[rt]=(s[ls[rt]]+s[rs[rt]]);
}
bool cmp(int rt,int rt1,int l,int r){
if(!rt)return 0;if(!rt1) return 1;
if(l==r){if(s[rt]>s[rt1])return 1;return 0;}
if(val[rs[rt]]!=val[rs[rt1]])return cmp(rs[rt],rs[rt1],mid+1,r);
return cmp(ls[rt],ls[rt1],l,mid);
}
void dfs(int rt,int l,int r){
if(!rt)return ;
if(l==r){for(int i=1;i<=s[rt];i++)cout<<l<<" ";return;}
dfs(rs[rt],mid+1,r),dfs(ls[rt],l,mid);
}
void solve(){
tot=0;
n=read(),L=read(),R=read();
while(!q.empty())q.pop_back();
while(!q2.empty())q2.pop();
for(int i=1;i<=n;i++)pw[i]=1ll*pw[i-1]*base%mod;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++){
b[i]=read();
if(n>50)cout<<b[i]<<" ";
}cout<<endl;
add(Rt[n],0,1,n,b[n]);q2.push(n);
for(int i=n-1;i>=1;i--){
while(!q2.empty()&&a[q2.front()]>=a[i]+L){
int z=q2.front();q2.pop();//cout<<z<<" "<<L<<" "<<a[i]<<endl;
while(!q.empty()&&cmp(Rt[z],Rt[q.back()],1,n))q.pop_back();
q.push_back(z);
}
while(!q.empty()&&a[q.front()]>a[i]+R){
q.pop_front();
}
if(!q.size()){if(i==1){puts("-1");return ;}continue;}
int x=q.front();
//cout<<i<<" "<<x<<endl;
add(Rt[i],Rt[x],1,n,b[i]);
q2.push(i);
}
cout<<s[Rt[1]]<<endl;
dfs(Rt[1],1,n);cout<<endl;
}
signed main(){
T=read();
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: 17924kb
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:
3 5 4 3 -1
result:
wrong answer 1st lines differ - expected: '3', found: ''