QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#518498#6400. Game: Celestelouhao088WA 162ms17944kbC++232.3kb2024-08-13 21:07:212024-08-13 21:07:23

Judging History

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

  • [2024-08-13 21:07:23]
  • 评测
  • 测评结果:WA
  • 用时:162ms
  • 内存:17944kb
  • [2024-08-13 21:07:21]
  • 提交

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 '