QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#241773 | #6400. Game: Celeste | ucup-team902# | WA | 273ms | 209968kb | C++14 | 5.2kb | 2023-11-06 17:06:15 | 2023-11-06 17:06:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define y1 shinkle
#define fi first
#define se second
#define bg begin
namespace IO{
#define gc getchar
inline int read(){
char ch=gc();
int res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
return f?res:-res;
}
inline ll readll(){
char ch=gc();
ll res=0;bool f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res*10)+(ch^48),ch=gc();
return f?res:-res;
}
inline char readchar(){
char ch=gc();
while(isspace(ch))ch=gc();
return ch;
}
inline int readstring(char *s){
int top=0;char ch=gc();
while(isspace(ch))ch=gc();
while(!isspace(ch)&&ch!=EOF)s[++top]=ch,ch=gc();
s[top+1]='\0';return top;
}
}
using IO::read;
using IO::readll;
using IO::readchar;
using IO::readstring;
template<typename tp>inline void chemx(tp &a,tp b){(a<b)?(a=b):0;}
template<typename tp>inline void chemn(tp &a,tp b){(a>b)?(a=b):0;}
cs int mod1=998244353,mod2=1e9+9;
inline int add(int a,int b,int mod){return (a+b)>=mod?(a+b-mod):(a+b);}
inline int dec(int a,int b,int mod){return (a<b)?(a-b+mod):(a-b);}
inline int mul(int a,int b,int mod){static ll r;r=(ll)a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b,int mod){a=(a+b)>=mod?(a+b-mod):(a+b);}
inline void Dec(int &a,int b,int mod){a=(a<b)?(a-b+mod):(a-b);}
inline void Mul(int &a,int b,int mod){static ll r;r=(ll)a*b;a=(r>=mod)?(r%mod):r;}
struct node{
int x,y;
node(int _x=0,int _y=0):x(_x),y(_y){}
friend inline node operator +(cs node &a,cs node &b){
return node(add(a.x,b.x,mod1),add(a.y,b.y,mod2));
}
friend inline node operator -(cs node &a,cs node &b){
return node(dec(a.x,b.x,mod1),dec(a.y,b.y,mod2));
}
friend inline node operator *(cs node &a,cs node &b){
return node(mul(a.x,b.x,mod1),mul(a.y,b.y,mod2));
}
friend inline bool operator ==(cs node &a,cs node &b){
return (a.x==b.x)&&(a.y==b.y);
}
};
cs int N=1000005;
node pw[N];
vector<int> ans;
namespace seg1{
cs int M=N*25;
int tot;
int lc[M],rc[M];
node tr[M];
void build(){
for(int i=1;i<=tot;i++)lc[i]=rc[i]=0,tr[i].x=tr[i].y=0;
tot=0;
}
int copy(int r){
int u=++tot;
lc[u]=lc[r],rc[u]=rc[r],tr[u]=tr[r];
return u;
}
void insert(int &u,int l,int r,int p){
u=copy(u);
if(l==r){
tr[u].x++,tr[u].y++;
return;
}
int mid=(l+r)/2;
if(p<=mid)insert(lc[u],l,mid,p);
else insert(rc[u],mid+1,r,p);
tr[u]=tr[lc[u]]*pw[r-mid]+tr[rc[u]];
}
bool find(int r1,int r2,int l,int r){
if(l==r){
return tr[r1].x<tr[r1].x;
}
if(tr[r1]==tr[r2])return 0;
int mid=(l+r)/2;
if(tr[rc[r1]]==tr[rc[r2]])return find(lc[r1],lc[r2],l,mid);
return find(rc[r1],rc[r2],mid+1,r);
}
void collect(int u,int l,int r){
if(!u)return;
if(l==r){
for(int i=1;i<=tr[u].x;i++)ans.pb(l);
return;
}
int mid=(l+r)/2;
collect(rc[u],mid+1,r);
collect(lc[u],l,mid);
}
}
int n,L,R;
int rt[N];
int x[N],a[N];
namespace seg2{
int mx[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
void pushup(int u){
if(mx[lc]==-1&&mx[rc]==-1){
mx[u]=-1;return;
}
if(mx[lc]==-1){
mx[u]=mx[rc];
return;
}
if(mx[rc]==-1){
mx[u]=mx[lc];
return;
}
mx[u]=(seg1::find(rt[mx[lc]],rt[mx[rc]],1,n)?mx[rc]:mx[lc]);
}
void build(int u,int l,int r){
mx[u]=-1;
if(l==r)return;
build(lc,l,mid);
build(rc,mid+1,r);
}
void insert(int u,int l,int r,int p){
if(l==r){
mx[u]=l;
return;
}
if(p<=mid)insert(lc,l,mid,p);
else insert(rc,mid+1,r,p);
pushup(u);
}
int query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des)return mx[u];
if(des<=mid)return query(lc,l,mid,st,des);
if(mid<st)return query(rc,mid+1,r,st,des);
int x1=query(lc,l,mid,st,des),x2=query(rc,mid+1,r,st,des);
if(x1==-1)return x2;
if(x2==-1)return x1;
return seg1::find(rt[x1],rt[x2],1,n)?x2:x1;
}
#undef lc
#undef rc
#undef mid
}
void solve(){
n=read(),L=read(),R=read();
for(int i=1;i<=n;i++)x[i]=read();
for(int i=1;i<=n;i++)a[i]=read();
seg1::build();
seg2::build(1,1,n);
rt[1]=0;
seg1::insert(rt[1],1,n,a[1]);
seg2::insert(1,1,n,1);
for(int i=2;i<=n;i++){
rt[i]=-1;
int pl=x[i]-R,pr=x[i]-L;
// cout<<pl<<" "<<pr<<'\n';
int p1=lower_bound(x+1,x+i+1,pl)-x;
int p2=upper_bound(x+1,x+i+1,pr)-x-1;
// cout<<i<<" "<<p1<<" "<<p2<<'\n';
if(p1<=p2){
int res=seg2::query(1,1,n,p1,p2);
// cout<<i<<" "<<res<<'\n';
if(res!=-1){
rt[i]=rt[res];
seg1::insert(rt[i],1,n,a[i]);
seg2::insert(1,1,n,i);
}
}
}
if(rt[n]==-1){
puts("-1");
}
else{
seg1::collect(rt[n],1,n);
cout<<ans.size()<<'\n';
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i+1==ans.size())cout<<'\n';
else cout<<" ";
}
}
ans.clear();
memset(rt,0,sizeof(int)*(n+1));
}
int main(){
#ifdef Stargazer
freopen("1.in","r",stdin);
#endif
int T=read();
node bs=node(31,37);
pw[0]=node(1,1);
for(int i=1;i<N;i++)pw[i]=pw[i-1]*bs;
while(T--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 19ms
memory: 209196kb
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: 273ms
memory: 209968kb
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:
7 16 16 11 10 7 6 3 -1 4 5 3 1 1 -1 32 20 20 20 20 19 19 19 17 17 16 15 15 14 12 12 11 11 10 10 10 10 9 9 7 7 6 6 6 5 3 2 1 17 19 19 19 19 15 14 12 9 9 8 6 6 5 3 3 2 1 -1 82 20 20 20 20 20 18 18 18 18 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 14 14 14 14 14 14 13 13 13 13 12 12 12 12 12 12 11 11 ...
result:
wrong answer 2nd lines differ - expected: '20 20 19 14 12 11 3', found: '16 16 11 10 7 6 3'