QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490867 | #8780. Training, Round 2 | yqh2025 | RE | 0ms | 0kb | C++14 | 1.2kb | 2024-07-25 16:36:39 | 2024-07-25 16:36:40 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
int n,a,b;
int la[N],ra[N],lb[N],rb[N];
int f[N][N];
set<int>s[N];
void solve(int l,int r,int id){
set<int>::iterator it=s[id].lower_bound(l);
vector<int>ve;
for(;it!=s[id].end()&&(*it)<=r;it++){
int x=*it;ve.push_back(x+1);
f[id][x+1]=f[id+1][x]=1;
s[id+1].insert(x);
}
while(1){
it=s[id].lower_bound(l);
if(it==s[id].end())break;
if((*it)>r)break;
s[id].erase(*it);
}
for(int x:ve)s[id].insert(x);
}
signed main(){
scanf("%lld%lld%lld",&n,&a,&b);
for(int i=1;i<=n;i++){
scanf("%lld%lld%lld%lld",&la[i],&ra[i],&lb[i],&rb[i]);
la[i]-=a,ra[i]-=a,lb[i]-=b,rb[i]-=b;
la[i]=max(la[i],0ll),ra[i]=max(ra[i],0ll);
lb[i]=max(lb[i],0ll),rb[i]=max(rb[i],0ll);
la[i]=min(la[i],n),ra[i]=min(ra[i],n);
lb[i]=min(lb[i],n),rb[i]=min(rb[i],n);
}
f[0][0]=1;s[0].insert(0);
for(int t=1;t<=n;t++){
for(int i=la[i];i<=ra[i];i++){
solve(lb[i],rb[i],i);
}
// for(int i=0;i<=n;i++){
// for(int j=0;j<=n;j++){
// cout<<f[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
}
int ans=0;
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(f[i][j])ans=max(ans,i+j);
}
}
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 0 0 0 1 0 1 1 1 0 1 1 1 1 1