QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#465343#8831. Chemistry Classucup-team3548#WA 144ms17240kbC++171.9kb2024-07-06 20:09:552024-07-06 20:09:55

Judging History

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

  • [2024-07-06 20:09:55]
  • 评测
  • 测评结果:WA
  • 用时:144ms
  • 内存:17240kb
  • [2024-07-06 20:09:55]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#define ll long long
#define LPos (Pos<<1)
#define RPos (LPos|1)
#define Mid ((L+R)>>1)
using namespace std;
int N;
ll Num[400001];
int DP[400001];
ll A,B;
int T;
int Tree[1600001];
int Tag[3200001];
bool Change[400001];
void Pushup(int Pos)
{
	Tree[Pos]=max(Tree[LPos],Tree[RPos]);
}
void Down(int Pos)
{
	Tree[Pos]+=Tag[Pos];
	Tag[LPos]+=Tag[Pos];
	Tag[RPos]+=Tag[Pos];
	Tag[Pos]=0;
}
void Pushdown(int Pos)
{
	if(Tag[LPos])Down(LPos);
	if(Tag[RPos])Down(RPos);
}
void Update(int L,int R,int Pos,int UL,int UR,int Add)
{
	if(L>=UL&&R<=UR)
	{
		Tree[Pos]+=Add;
		Tag[LPos]+=Add;
		Tag[RPos]+=Add;
		return;
	}
	Pushdown(Pos);
	if(Mid>=UL)Update(L,Mid,LPos,UL,UR,Add);
	if(Mid<UR)Update(Mid+1,R,RPos,UL,UR,Add);
	Pushup(Pos);
}
int Query(int L,int R,int Pos,int QL,int QR)
{
	if(L>=QL&&R<=QR)
	return Tree[Pos];
	Pushdown(Pos);
	int Res=0;
	if(Mid>=QL)Res=Query(L,Mid,LPos,QL,QR);
	if(Mid<QR)Res=max(Res,Query(Mid+1,R,RPos,QL,QR));
	return Res;
}
void Build(int L,int R,int Pos)
{
	Tree[Pos]=Tag[LPos]=Tag[RPos]=0;
	if(L==R)return;
	Build(L,Mid,LPos);
	Build(Mid+1,R,RPos);
}
void Clear()
{
	Build(0,N-1,1);
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%lld%lld",&N,&A,&B);
		Clear();
		for(int i=1;i<=N<<1;++i)
		scanf("%lld",&Num[i]);
		sort(Num+1,Num+(N<<1)+1);
		int Left=1;
		for(int i=1;i<=N<<1;i+=2)
		{
			if(i>2)
			Change[i]=(Num[i]-Num[i-1]<=B);
			if(Num[i+1]-Num[i]>A)
			{
				puts("-1");
				goto Next;
			}
		}
		for(int i=1;i<=N<<1;i+=2)
		{
			while(Num[i]-Num[Left]>A)
			Left+=2;
			if(i>1)
			DP[i]=DP[i-2]+(Num[i+1]-Num[i]<=B);
			else DP[i]=(Num[i+1]-Num[i]<=B);
			if(Change[i])
			Update(0,N-1,1,0,(i>>1)-1,1);
			if(Left<i)
			DP[i]=max(Query(0,N-1,1,Left>>1,(i>>1)-1),DP[i]);
			if(i<N<<1)
			Update(0,N-1,1,(i>>1)+1,(i>>1)+1,DP[i]);
		}
		printf("%d\n",DP[(N<<1)-1]);
		Next:;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7692kb

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: 0
Accepted
time: 110ms
memory: 17240kb

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 112ms
memory: 15200kb

input:

1
199998 38987266278826 1
974183459404323858 517476981059568123 730207399881008603 532509909948600146 89227878552241675 16653300445469756 791674368913652595 92177901403222015 980536748304824579 581564387828767376 471919726893404451 759601909683722004 632340812998214017 818440789777778368 18845836031...

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 104ms
memory: 15172kb

input:

1
199996 54170919220045 1
968843690955781467 596307347951820347 406785475849275444 383666938223357986 725160735782817082 132577412512120631 891899794864087098 779434145671998619 932681297277907326 208765550447928461 385078857912267975 669360937040314510 917331948890514855 505938744714587815 47145437...

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: -100
Wrong Answer
time: 144ms
memory: 17228kb

input:

1
199998 35667463938291 8255384928693
770468016026697053 519790816750772730 110085058423772871 85144239858008037 782003096084947976 938498644167289660 693768718229582367 242186248813489674 155335549252315364 428982852761422230 890445026369869037 86401573937739054 9122788624365829 63351367715811463 1...

output:

193758

result:

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