QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#142028 | #6400. Game: Celeste | Schi2oid | ML | 0ms | 0kb | C++14 | 2.4kb | 2023-08-18 11:15:30 | 2023-08-18 11:15:31 |
answer
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
mt19937 ra(time(0));
ull val[1000005];
int a[1000005],b[1000005],bcnt=0;
int x[1000005];
#define mid ((l+r)>>1)
struct node{
int cnt,ls,rs;
ull hx;
node(int CNT=0,int LS=0,int RS=0,ull HX=0){
cnt=CNT,ls=LS,rs=RS,hx=HX;
}
}t[50000005];
int rt[2000005];
int idcnt=0;
void build(int &x){x=++idcnt;}
void push_up(int p){t[p].hx=t[t[p].ls].hx+t[t[p].rs].hx,t[p].cnt=t[t[p].ls].cnt+t[t[p].rs].cnt;}
void modi(int p,int q,int l,int r,int x){
if(l==r){
t[q].hx=t[p].hx+val[l];
t[q].cnt=t[p].cnt+1;
return;
}
t[q].ls=t[p].ls,t[q].rs=t[p].rs;
if(x<=mid) build(t[q].ls),modi(t[p].ls,t[q].ls,l,mid,x);
else build(t[q].rs),modi(t[p].rs,t[q].rs,mid+1,r,x);
push_up(q);
}
int find_pos(int p,int q,int l,int r){
if(t[p].hx==t[q].hx) return -1;
if(l==r) return l;
if(t[t[p].rs].hx==t[t[q].rs].hx) return find_pos(t[p].ls,t[q].ls,l,mid);
else return find_pos(t[p].rs,t[q].rs,mid+1,r);
}
int query(int p,int l,int r,int q){
if(l==r) return t[p].cnt;
if(q<=mid) return query(t[p].ls,l,mid,q);
else return query(t[p].rs,mid+1,r,q);
}
bool leq(int x,int y){
int p=find_pos(x,y,1,bcnt);
if(p==-1) return 0;
else return query(x,1,bcnt,p)<query(y,1,bcnt,p);
}
void prt(int p,int l,int r){
if(!p) return;
if(l==r) for(int i=1;i<=t[p].cnt;i++) printf("%d ",b[l]);
prt(t[p].rs,mid+1,r);
prt(t[p].ls,l,mid);
}
deque<int>dq;
int main(){
int T,n,l,r;
cin>>T;
while(T--){
scanf("%d%d%d",&n,&l,&r);
for(int i=1;i<=idcnt;i++) t[i]=node(0,0,0,0);
dq.clear();
bcnt=idcnt=0;
for(int i=1;i<=n;i++) rt[i]=-1;
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[++bcnt]=a[i];
}
sort(b+1,b+1+bcnt);
bcnt=unique(b+1,b+1+bcnt)-b-1;
for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+bcnt,a[i])-b;
for(int i=1;i<=bcnt;i++) val[i]=ra()*ra();
build(rt[1]);
modi(0,rt[1],1,bcnt,a[1]);
int pt=0;
for(int i=2;i<=n;i++){
while(x[pt+1]<=x[i]-l){
pt++;
if(rt[pt]!=-1){
while((!dq.empty())&&leq(rt[dq.back()],rt[pt])) dq.pop_back();
dq.push_back(pt);
}
}
while((!dq.empty())&&x[dq.front()]<x[i]-r) dq.pop_front();
if(dq.size()){
build(rt[i]);
modi(rt[dq.front()],rt[i],1,bcnt,a[i]);
}
}
if(rt[n]==-1){
puts("-1");
continue;
}
printf("%d\n",t[rt[n]].cnt);
prt(rt[n],1,bcnt);
puts("");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3