QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#518498 | #6400. Game: Celeste | louhao088 | WA | 162ms | 17944kb | C++23 | 2.3kb | 2024-08-13 21:07:21 | 2024-08-13 21:07:23 |
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]<<" ";
}if(n>=50)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: 100
Accepted
time: 0ms
memory: 17944kb
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:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 162ms
memory: 17908kb
input:
10000 57 8 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...
output:
11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 11 2 15 11 19 5 16 4 3 7 20 11 11 11 3 2 1 12 19 12 3 4 11 5 5 11 20 8 6 6 4 11 4 4 3 13 11 7 20 6 10 12 14 10 1 7 11 6 13 20 9 2 15 7 16 17 1 13 17 17 15 17 11 8 11 4 1 19 14...
result:
wrong answer 1st lines differ - expected: '7', found: '11 16 7 7 10 13 9 14 10 1 12 4... 7 20 9 11 2 15 11 19 5 16 4 3 '