QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#518497#6400. Game: Celestelouhao088WA 0ms17924kbC++232.3kb2024-08-13 21:06:522024-08-13 21:06:52

Judging History

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

  • [2024-08-13 21:06:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:17924kb
  • [2024-08-13 21:06:52]
  • 提交

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: ''