QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#47340 | #4674. Lots Of Tasks | aurelion_sol | WA | 2ms | 3776kb | C++14 | 1.4kb | 2022-09-08 11:35:21 | 2022-09-08 11:35:22 |
Judging History
answer
#include<bits/stdc++.h>
#define rp(i,a,b) for(int i=a,_=b;i<=_;++i)
#define pr(i,a,b) for(int i=a,_=b;i>=_;--i)
#define pb push_back
using namespace std;
typedef vector<int> VI;
const int N=205;
int n,m,cnt[3*N],sum[3*N],bg[2*N],ed[2*N];
bool dp[2*N][3*N];
VI tmp;
struct range{
int l,r,id;
bool operator<(const range &o)const{return l<o.l||(l==o.l&&r<o.r);}
}a[2*N];
inline int get(int x){return lower_bound(tmp.begin(),tmp.end(),x)-tmp.begin()+1;}
int main(){
scanf("%d",&n),n*=2;
for(int i=1;i<=n;i+=2){
scanf("%d%d",&a[i].l,&a[i+1].r);
a[i].r=a[i+1].l=(a[i].l+a[i+1].r)>>1;
}
rp(i,1,n)a[i].id=i,tmp.pb(a[i].l),tmp.pb(a[i].r);
sort(tmp.begin(),tmp.end());
tmp.resize(unique(tmp.begin(),tmp.end())-tmp.begin());
m=tmp.size();
rp(i,1,n)++cnt[a[i].l=get(a[i].l)],--cnt[a[i].r=get(a[i].r)];
rp(i,1,m)cnt[i]+=cnt[i-1];
rp(i,1,m)sum[i]=sum[i-1]+((!cnt[i])!=(!cnt[i-1]));
sort(a+1,a+n+1);
bool ans=0;
rp(i,1,n){
bg[i]=cnt[a[i].l]&&!cnt[a[i].l-1]?sum[a[i].l]:-1;
ed[i]=!cnt[a[i].r]&&cnt[a[i].r-1]?sum[a[i].r]:-1;
if(bg[i]==1){
dp[i][a[i].l]=1;
}
rp(k,a[i].l,a[i].r-1)if(dp[i][k]){
rp(j,i+1,n)if(a[j].l>k&&a[j].l<=a[i].r&&a[j].r>a[i].r&&a[i].id!=a[j].id-1)dp[j][a[i].r]=1;
}
if(~ed[i]){
bool b=0;
rp(k,a[i].l,a[i].r-1)if(dp[i][k]){b=1;break;}
if(!b)continue;
if(ed[i]==sum[m])ans=1;
rp(j,i+1,n)if(bg[j]==ed[i]+1)dp[j][a[j].l]=1;
}
}
puts(ans?"YES":"NO");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3564kb
input:
4 1 9 5 13 11 13 6 12
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
3 46 76 0 2 45 75
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
10 364982626 705073316 215175753 478059739 828386201 994402901 910820793 911394551 266699249 426536243 719535057 815124115 623551500 911107672 705073316 733996798 93555423 439843075 421091507 535027971
output:
YES
result:
ok answer is YES
Test #4:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
10 51835689 620807443 750787525 796909711 513533935 575395493 541578125 684873005 537565421 613225565 617887598 929809638 255789102 452077882 336321566 371545418 684873005 816702045 359691050 544464714
output:
YES
result:
ok answer is YES
Test #5:
score: 0
Accepted
time: 2ms
memory: 3608kb
input:
8 572132975 786288271 467448988 567426274 105311006 105804388 82568617 105557697 105804388 483353486 127607255 517437631 455641925 679210623 266635431 322522443
output:
NO
result:
ok answer is NO
Test #6:
score: 0
Accepted
time: 2ms
memory: 3776kb
input:
8 148459525 345343515 502457315 746706787 288511258 298478650 276770399 417832891 246901520 330120996 294124965 347301645 417832891 587081739 293494954 347931656
output:
NO
result:
ok answer is NO
Test #7:
score: 0
Accepted
time: 2ms
memory: 3736kb
input:
9 166442441 389739205 7943919 166442441 286208703 431033671 431033671 456326329 241885163 330226185 278090823 294020525 84893800 89492560 443680000 749236104 330226185 387016189
output:
NO
result:
ok answer is NO
Test #8:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
9 282962511 581565901 181537158 549056140 662985805 666211931 480229505 852194357 773418109 939896935 103399690 259674626 298329092 432264206 852194357 861120687 498532934 664598868
output:
YES
result:
ok answer is YES
Test #9:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
10 552212097 559434409 632141489 650923207 768930601 851058249 83468611 310952913 514134095 768930601 19285638 63747984 41516811 125420411 507571217 604075289 486727329 632141489 197210762 817931672
output:
NO
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
10 861285491 928841189 8619266 43933564 34883256 974780518 895063340 949668240 504831887 662689811 468624021 698897677 26276415 36906263 536509863 861285491 895880341 948851239 31591339 38175173
output:
NO
result:
ok answer is NO
Test #11:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
9 79 113 50 78 14 76 62 66 77 79 0 6 96 98 3 25 28 62
output:
NO
result:
ok answer is NO
Test #12:
score: 0
Accepted
time: 2ms
memory: 3664kb
input:
8 57 69 41 55 59 63 29 31 30 62 46 50 69 97 55 67
output:
NO
result:
ok answer is NO
Test #13:
score: -100
Wrong Answer
time: 2ms
memory: 3708kb
input:
10 1 3 2 64 8 58 58 86 71 73 72 74 61 87 81 93 92 94 88 100
output:
NO
result:
wrong answer expected YES, found NO