QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#465343 | #8831. Chemistry Class | ucup-team3548# | WA | 144ms | 17240kb | C++17 | 1.9kb | 2024-07-06 20:09:55 | 2024-07-06 20:09:55 |
Judging History
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'