QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#241773#6400. Game: Celesteucup-team902#WA 273ms209968kbC++145.2kb2023-11-06 17:06:152023-11-06 17:06:16

Judging History

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

  • [2023-11-06 17:06:16]
  • 评测
  • 测评结果:WA
  • 用时:273ms
  • 内存:209968kb
  • [2023-11-06 17:06:15]
  • 提交

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;
}

詳細信息

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'