QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#166959 | #6400. Game: Celeste | qzzyq | WA | 186ms | 16280kb | C++14 | 3.4kb | 2023-09-06 21:39:38 | 2023-09-06 21:39:38 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
int f=1;x=0;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
x*=f;
}
namespace Debug{
Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
int sum=1;
while (y) {
if (y&1) sum=sum*x%mod;
x=x*x%mod;y>>=1;
}
return sum;
}
mt19937 rnd(time(0));
int n,L,R;
int q[maxn],head,tail;
int a[maxn],c[maxn];
unsigned val[maxn];
int root[maxn],cnt,fl[maxn];
struct yyy{
int ls,rs,siz;
unsigned sum;
}f[maxn*20];
int Update(int l,int r,int pre,int k) {
int rt=++cnt;f[rt]=f[pre];
if (l==r) return f[rt].siz++,f[rt].sum+=val[k],rt;
int mid=l+r>>1;
if (k<=mid) f[rt].ls=Update(l,mid,f[rt].ls,k);
else f[rt].rs=Update(mid+1,r,f[rt].rs,k);
f[rt].sum=f[f[rt].ls].sum^f[f[rt].rs].sum;
f[rt].siz=f[f[rt].ls].siz+f[f[rt].rs].siz;
return rt;
}
bool find(int l,int r,int rt1,int rt2) {
if (l==r) return f[rt1].siz>f[rt2].siz;
int mid=l+r>>1;
if (f[f[rt1].rs].sum==f[f[rt2].rs].sum) return find(l,mid,f[rt1].ls,f[rt2].ls);
else return find(mid+1,r,f[rt1].rs,f[rt2].rs);
}
int Query(int l,int r,int rt,int k) {
if (!f[rt].siz) return 0;
if (l==r) return l;
int mid=l+r>>1;
if (r<=k) {
if (f[f[rt].rs].siz) return Query(mid+1,r,f[rt].rs,k);
else return Query(l,mid,f[rt].ls,k);
}
int tmp1=0,tmp2=0;
if (mid<k) tmp1=Query(mid+1,r,f[rt].rs,k);
if (tmp1) return tmp1;
tmp2=Query(l,mid,f[rt].ls,k);
return tmp2;
}
bool cmp(int x,int y) {
return find(1,n,root[x],root[y]);
// int id=find(1,n,root[x],root[y]);
// int tmp1=Query(1,n,root[x],id);
// int tmp2=Query(1,n,root[y],id);
// return tmp1>tmp2;
}
void print(int l,int r,int rt) {
// gdb(l,r,f[f[rt].ls].siz,f[f[rt].rs].siz);
if (l==r) {
for (int i=1;i<=f[rt].siz;i++) printf("%d ",l);
return ;
}
int mid=l+r>>1;
if (f[f[rt].rs].siz) print(mid+1,r,f[rt].rs);
if (f[f[rt].ls].siz) print(l,mid,f[rt].ls);
}
void solve(void) {
int i,j,las=0;
read(n);read(L);read(R);
for (i=1;i<=n;i++) root[i]=fl[i]=0;cnt=0;
for (i=1;i<=n;i++) read(c[i]);
for (i=1;i<=n;i++) read(a[i]);
for (i=1;i<=n;i++) val[i]=rnd();
root[1]=Update(1,n,root[1],a[1]);
q[head=tail=1]=1;las=1;
for (i=2;i<=n;i++) {
int ls=lower_bound(c+1,c+1+n,c[i]-R)-c;
int rs=lower_bound(c+1,c+1+n,c[i]-L+1)-c-1;
if (ls>rs) continue;
for (j=las+1;j<=rs;j++) {
while (head<=tail&&cmp(q[tail],j)==0) tail--;
q[++tail]=j;
}
while (head<=tail&&q[head]<ls) head++;
las=rs;
if (q[head]<=rs) {
root[i]=Update(1,n,root[q[head]],a[i]);
// gdb(i,q[head],a[i]);
fl[i]=1;
// print(1,n,root[i]);put();
}
}
if (fl[n]) printf("%d\n",f[root[n]].siz),print(1,n,root[n]),put();
else puts("-1");
}
signed main(void){
int T;read(T);while (T--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 16012kb
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: 186ms
memory: 16280kb
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 20 20 19 14 12 11 3 26 20 16 16 15 15 14 13 13 12 11 11 8 8 7 7 6 6 5 5 4 4 4 4 4 2 1 6 6 5 3 2 1 1 8 19 18 17 11 10 9 7 7 185 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15...
result:
wrong answer 3rd lines differ - expected: '-1', found: '26'