QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#458030 | #8831. Chemistry Class | ucup-team3586# | WA | 26ms | 10048kb | C++23 | 1.9kb | 2024-06-29 15:26:34 | 2024-06-29 15:26:35 |
Judging History
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'