QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#47340#4674. Lots Of Tasksaurelion_solWA 2ms3776kbC++141.4kb2022-09-08 11:35:212022-09-08 11:35:22

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-08 11:35:22]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3776kb
  • [2022-09-08 11:35:21]
  • 提交

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;
}

详细

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