QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#142016#6400. Game: CelesteSchi2oidWA 195ms473844kbC++142.5kb2023-08-18 11:02:022023-08-18 11:02:03

Judging History

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

  • [2023-08-18 11:02:03]
  • 评测
  • 测评结果:WA
  • 用时:195ms
  • 内存:473844kb
  • [2023-08-18 11:02:02]
  • 提交

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[20000005];
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++;
		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;
		//cerr<<t[rt[1]].cnt<<endl;
		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()){
				//cerr<<i<<" "<<dq.front()<<endl;
				build(rt[i]);
				modi(rt[dq.front()],rt[i],1,bcnt,a[i]);
				//cerr<<t[rt[i]].cnt<<endl;
			}
		}
		if(rt[n]==-1){
			puts("-1");
			continue;
		}
		printf("%d\n",t[rt[n]].cnt);
		prt(rt[n],1,bcnt);
		puts("");
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 16ms
memory: 473844kb

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: 195ms
memory: 473004kb

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 19 12 11 8 7 3 
-1
5
6 5 3 2 1 
-1
19
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 3 2 1 
13
20 19 18 17 16 15 14 9 6 5 4 3 2 
-1
20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 
12
20 18 17 16 15 13 11 10 8 7 6 2 
8
20 19 15 14 13 11 10 2 
12
20 19 18 17 16 15 11 10 9 7 2 1 
8
20 18 16 14 ...

result:

wrong answer 2nd lines differ - expected: '20 20 19 14 12 11 3', found: '20 19 12 11 8 7 3 '