QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#458030#8831. Chemistry Classucup-team3586#WA 26ms10048kbC++231.9kb2024-06-29 15:26:342024-06-29 15:26:35

Judging History

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

  • [2024-06-29 15:26:35]
  • 评测
  • 测评结果:WA
  • 用时:26ms
  • 内存:10048kb
  • [2024-06-29 15:26:34]
  • 提交

answer

//Code by dXqwq, who is still searching painless suicide.
#include<bits/stdc++.h>
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define int long long
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int p=998244353;
int qp(int x,int y)
{
	int res=1;
	for(int t=x; y; y>>=1,t=1ll*t*t%p)
		if(y&1) res=1ll*res*t%p;
	return res;
}
int a[1<<20],b[1<<20],f[1<<20],g[1<<20];
void update(int nl,int nr,int t,int x,int k)
{
	if(nl==nr){g[x]=k;return;}
	int mid=(nl+nr)>>1;
	if(t<=mid) update(nl,mid,t,x<<1,k);
	else update(mid+1,nr,t,(x<<1)+1,k);
	g[x]=min(g[x<<1],g[(x<<1)+1]);
}
int query(int nl,int nr,int l,int r,int x)
{
	if(r<nl||nr<l) return 1e18;
	if(l<=nl&&nr<=r) return g[x];
	int mid=(nl+nr)>>1;
	return min (query(nl,mid,l,r,x<<1),
	query(mid+1,nr,l,r,(x<<1)+1));
}
signed main()
{
	for(int T=read();T--;)
	{
		int n=read(),A=read(),B=read();
		for(int i=1; i<=n*2; ++i) a[i]=read();
		sort(a+1,a+n+1);
		int c=0,ok=0;
		for(int i=1; i<=n*2; ++i)
			if(a[i*2]-a[i*2-1]>A) ok=1;
		if(ok){puts("-1");continue;}
		b[1]=1;
		for(int i=2; i<=n*2; ++i)
			if(a[i]-a[i-1]<=B) b[i]=b[i-2];
			else b[i]=i;
		// memset(f,0x3f,sizeof(f));
		int m=1;
		while(m<n*2) m<<=1;
		for(int i=0; i<m*2; ++i) g[i]=1e18;
		update(0,n*2,0,1,0);
		for(int i=2,j=1; i<=n*2; i+=2)
		{
			while(a[i]-a[j]>A) ++j;
			//no
			f[i]=1e18;
			if(b[i]<i) f[i]=f[i-2];
			//yes
			int t=max(b[i-1],j)-1;
			// printf("%lld %lld\n",i,j);
			f[i]=min(f[i],query(0,n*2,t,n*2,1)+1);
		
			// for(int k=i-2; k>=t; k-=2)
				// f[i]=min(f[i],f[k]+1);
			// T[i&1].query
			update(0,n*2,i,1,f[i]);
		
		}
		printf("%lld\n",n-f[n*2]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 10048kb

input:

4
1 2 1
42 69
2 3 1
1 2 3 4
2 5 1
6 1 3 4
5 19 1
1 7 8 9 10 11 12 13 14 20

output:

-1
2
1
4

result:

ok 4 number(s): "-1 2 1 4"

Test #2:

score: -100
Wrong Answer
time: 26ms
memory: 7688kb

input:

1
199996 67013419502794 1
403716252634677166 895717933735068492 410002430455111886 844431179242134559 322988383133810700 133475121268220299 481706326769800263 606871141911985391 195911124687409946 959578180866483093 930547702157856949 877914383714875160 994158366044742636 890855755285236186 69498488...

output:

-1

result:

wrong answer 1st numbers differ - expected: '0', found: '-1'