QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#457955 | #8831. Chemistry Class | ucup-team1338# | RE | 0ms | 3796kb | C++20 | 1.6kb | 2024-06-29 14:57:03 | 2024-06-29 14:57:04 |
Judging History
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...