QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#457955#8831. Chemistry Classucup-team1338#RE 0ms3796kbC++201.6kb2024-06-29 14:57:032024-06-29 14:57:04

Judging History

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

  • [2024-06-29 14:57:04]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3796kb
  • [2024-06-29 14:57:03]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll a[maxn];int dp[maxn];
template<typename T,auto op,auto e>class segtree{//线段树,单点修改,区间查询。 
    int n=0;           // e 单位元 
    vector<T> v;
    void pushup(int k) {v[k]=op(v[k*2],v[k*2+1]);}
    void set(int i,int k,int l,int r,T x)
    {
    	int mid=(l+r)/2;
        if (l>k||r<k) return;
        if (l==r) {v[i]=x;return;}
        set(i*2,k,l,mid,x);set(i*2+1,k,mid+1,r,x);
        pushup(i);
    }
    T query(int i,int ql,int qr,int l,int r)
    {
    	int mid=(l+r)/2;
        if (l>qr||r<ql) return e();
        if (l>=ql&&r<=qr) return v[i];
        return op(query(i*2,ql,qr,l,mid),query(i*2+1,ql,qr,mid+1,r));
    }
    public:
    segtree(int n){this->n=n;v=vector<T>(n*4, e());} 
    void set(int l, T x) { set(1, l, 1, n, x); }//point change
    T query(int l, int r) {return query(1, l, r, 1, n);}// seg query
};    
void solve()
{
	int n;ll A,B;
	cin>>n>>A>>B;
	for(int i=1;i<=2*n;i++) scanf("%lld",&a[i]),dp[i]=0;
	sort(a+1,a+1+2*n);
	segtree<int,[](int a,int b){return max(a,b);},[](){return -1e9;}> t(2*n+5);
	int tot=0,flag=0;
	for(int i=1;i<=2*n;i++)
	{
		if(i&1)
		{
			if(i!=1) tot+=(a[i]-a[i-1])<=B;
			t.set(i,dp[i-1]-tot);
		}
		else
		{
			int pos=lower_bound(a+1,a+1+i,a[i]-A)-a;
			if(pos==i) 
			{
				flag=1;
				break;
			}
			dp[i]=t.query(pos,i-1)+tot;	
			pos=lower_bound(a+1,a+1+i,a[i]-B)-a;
			dp[i]=max(dp[i],t.query(pos,i-1)+1+tot);
		}
	}
	if(flag==1) printf("-1\n");
	else printf("%d\n",dp[n*2]);
}
int main()
{
	int t;cin>>t;
	while(t--) solve();
 } 

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

input:

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

output:


result: