QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#469129#6400. Game: Celeste233LTL 0ms18476kbC++143.2kb2024-07-09 14:43:282024-07-09 14:43:28

Judging History

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

  • [2024-07-09 14:43:28]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:18476kb
  • [2024-07-09 14:43:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define uint unsigned int
#define ldb long double
#define pii pair<int,int>
#define mkp make_pair
#define mkt make_tuple
#define fr first
#define se second
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
#define all(_box) _box.begin(),_box.end()
#define ppc __builtin_popcount
#define ctz __builtin_ctz
#define clz __builtin_clz
#define lbd lower_bound
#define ubd upper_bound
#define deb(x) cerr<<#x<<'='<<(x)<<' '
using namespace std;
const int base=1000999;
const int N=1e6+4;
ull pw[N];
int n;
int a[N],b[N];
vector<int>ans;

int rot[N];
namespace SMT{
    int cnt;
    struct node{
        int ls,rs,l,r;
        ull hash_val;
    }st[30*N];

    #define ls(id) st[id].ls
    #define rs(id) st[id].rs
    void push_up(int id){
        st[id].hash_val=st[ls(id)].hash_val*pw[st[rs(id)].r-st[rs(id)].l+1]+st[rs(id)].hash_val;
    }
    void build(int &id,int l,int r){
        assert(cnt+1<30*N);
        id=++cnt,st[id].l=l,st[id].r=r;
        if(l==r)return;
        int mid=(l+r)>>1;
        build(ls(id),l,mid);
        build(rs(id),mid+1,r);
    }
    void update(int &id,int pos){
        if(st[id].l>pos||st[id].r<pos)return;
        assert(cnt+1<30*N);
        st[++cnt]=st[id],id=cnt;
        if(st[id].l==st[id].r){
            st[id].hash_val++;
            return;
        }
        update(ls(id),pos);
        update(rs(id),pos);
        push_up(id);
    }
    bool comp_(int p,int q){//check if p>q
        if(st[p].l==st[p].r)
            return st[p].hash_val>st[q].hash_val;
        if(st[rs(p)].hash_val!=st[rs(q)].hash_val)
            return comp_(rs(p),rs(q));
        return comp_(ls(p),ls(q));
    }
    bool comp(int p,int q){
        if(st[p].hash_val==st[q].hash_val)return 0;
        return comp_(p,q);
    }
    void print(int id){
        if(st[id].l==st[id].r){
            for(int i=0;i<int(st[id].hash_val);i++)
                ans.push_back(st[id].l);
            return;
        }
        print(rs(id));
        print(ls(id));
    }
    #undef ls
    #undef rs
}
using SMT::update;
using SMT::comp;

void solve(){
    int l,r;
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    
    SMT::build(rot[1],1,n);
    update(rot[1],b[1]);
    deque<int>q;
    for(int i=2,p=1;i<=n;i++){
        while(a[i]-a[p]>=l){
            if(rot[p]){
                while(!q.empty()&&comp(rot[p],rot[q.back()]))q.pop_back();
                q.push_back(p);
            }
            p++;
        }
        while(!q.empty()&&a[i]-a[q.front()]>r)q.pop_front();
        if(q.empty())rot[i]=0;
        else update(rot[i]=rot[q.front()],b[i]);
    }
    if(!rot[n])cout<<-1<<'\n';
    else{
        ans.clear();
        SMT::print(rot[n]);
        cout<<ans.size()<<'\n';
        for(int i:ans)cout<<i<<' ';
        cout<<'\n';
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);

    pw[0]=1;
    for(int i=1;i<N;i++)
        pw[i]=pw[i-1]*base;

    int T;
    cin>>T;
    while(T--){
        SMT::cnt=0;
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 18476kb

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
Time Limit Exceeded

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:


result: