QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167947#6400. Game: CelesteqzzyqWA 189ms16520kbC++143.6kb2023-09-07 18:40:482023-09-07 18:40:49

Judging History

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

  • [2023-09-07 18:40:49]
  • 评测
  • 测评结果:WA
  • 用时:189ms
  • 内存:16520kb
  • [2023-09-07 18:40:48]
  • 提交

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;
	ll 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);
}
int T;
void solve(int Cas) {
	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]);
//	if (Cas==2&&T>=3) {
//		printf("%d %d %d\n",n,L,R);
//		for (i=1;i<=n;i++) printf("%d ",c[i]);put();
//		exit(0);
//	} 
	for (i=1;i<=n;i++) val[i]=rnd();
	root[1]=Update(1,n,root[1],a[1]);fl[1]=1;
	head=1;tail=0;
	las=0;
	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; 
		}
		las=rs;
		while (head<=tail&&q[head]<ls) head++;
		if (head<=tail) {
//			gdb(i,head,tail,q[head],q[tail]);
//			assert(ls<=q[head]);
//			assert(q[head]<=rs);
			root[i]=Update(1,n,root[q[head]],a[i]);
			fl[i]=1;			
		}
	}
	if (fl[n]) printf("%d\n",f[root[n]].siz),print(1,n,root[n]),put();
	else puts("-1");
}
signed main(void){
	read(T);
	for (int i=1;i<=T;i++) solve(i);
//	while (T--) solve();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 16092kb

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: 189ms
memory: 16520kb

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'