QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164067#5378. 匹配问题DaiRuiChen00716 325ms24696kbC++141.7kb2023-09-04 19:20:592023-09-04 19:20:59

Judging History

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

  • [2023-09-04 19:20:59]
  • 评测
  • 测评结果:16
  • 用时:325ms
  • 内存:24696kb
  • [2023-09-04 19:20:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5,W=1e6;
class SegmentTree {
	private:
		struct Node {
			int add,min;
		}	tr[MAXN<<3];
		inline int L(int p) { return p<<1; }
		inline int R(int p) { return p<<1|1; }
		inline void addtag(int p,int k) { tr[p].add+=k,tr[p].min+=k; }
		inline void pushup(int p) {
			tr[p].min=std::min(tr[L(p)].min,tr[R(p)].min);
		}
		inline void pushdown(int p) {
			addtag(L(p),tr[p].add),addtag(R(p),tr[p].add),tr[p].add=0;
		}
	public:
		inline void Modify(int ul,int ur,int k,int l=1,int r=W,int p=1) {
			if(ul<=l&&r<=ur) return addtag(p,k);
			int mid=(l+r)>>1;
			pushdown(p);
			if(ul<=mid) Modify(ul,ur,k,l,mid,L(p)); 
			if(mid<ur) Modify(ul,ur,k,mid+1,r,R(p));
			pushup(p);
		}
		inline int Query(int ul,int ur,int l=1,int r=W,int p=1) {
			if(ul<=l&&r<=ur) return tr[p].min;
			int mid=(l+r)>>1;
			pushdown(p);
			if(ur<=mid) return Query(ul,ur,l,mid,L(p));
			if(mid<ul) return Query(ul,ur,mid+1,r,R(p));
			return std::min(Query(ul,ur,l,mid,L(p)),Query(ul,ur,mid+1,r,R(p)));
		}
}	TR;
int a[MAXN],b[MAXN];
inline void add(int x,int v) { TR.Modify(x,W,v); }
signed main() {
	int n,ans=0,x,y;
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]); sort(a+1,a+n+1);
	for(int i=1;i<=n;++i) scanf("%d",&b[i]); sort(b+1,b+n+1);
	deque <int> B{b[n]}; add(b[n],1);
	for(int i=n,j=n;i;--i) {
		while(j>=1&&(B.empty()||B.front()>a[i]+y)) {
			add(a[--j]+x,-1),B.push_front(b[j]),add(b[j],1);
		}
		if(j>=1&&B.front()>=a[i]&&TR.Query(1,W)>=0) ++ans,add(B.front(),-1),B.pop_front();
		else add(B.back(),-1),B.pop_back();
		add(a[i]+x,1);
	}
	printf("%d\n",ans);
	return 0;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 4
Accepted
time: 1ms
memory: 5904kb

input:

2 2 1
1 1
1 1

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 6628kb

input:

10 200000 100000
34181 300096 24293 22680 402306 193269 438170 254676 188147 73971
216849 477743 461911 135785 467234 278230 287107 223666 124173 135091

output:

7

result:

ok single line: '7'

Test #3:

score: -4
Wrong Answer
time: 3ms
memory: 6392kb

input:

10 200000 50000
298370 136488 436143 52173 206095 140981 321188 407844 342157 193338
138374 383207 156748 442404 386749 492604 354156 229996 447123 418264

output:

6

result:

wrong answer 1st lines differ - expected: '5', found: '6'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 16
Accepted

Test #100:

score: 16
Accepted
time: 302ms
memory: 24696kb

input:

500000 500000 10
200184 74991 71203 334998 316800 34483 120570 301054 331108 232072 189788 397143 490296 56807 361700 88818 42376 460305 371750 450351 338384 429789 426045 445029 152316 408919 188124 144966 457495 475025 225370 260510 383159 495247 54319 246245 240728 372033 439599 119720 449020 451...

output:

312193

result:

ok single line: '312193'

Test #101:

score: 0
Accepted
time: 325ms
memory: 24224kb

input:

500000 500000 50
115284 354660 85605 451547 440275 269883 210494 181791 97169 97532 263985 106346 124476 164126 381493 219782 163879 157204 143832 387279 4369 170920 162107 286628 360679 297015 162335 375991 432661 437537 428657 490336 278522 452496 405280 362156 51892 437590 365597 224799 139341 44...

output:

315815

result:

ok single line: '315815'

Test #102:

score: 0
Accepted
time: 295ms
memory: 24580kb

input:

500000 500000 10
247245 32538 32538 32538 66100 116348 489150 32538 32538 337592 32538 32538 265870 127367 424999 32538 32538 249591 32538 32538 32538 2915 32538 312118 98677 32538 82852 246210 127902 102568 32538 474775 433925 32538 32538 477886 32538 240095 490687 152275 32538 177319 380963 150554...

output:

382878

result:

ok single line: '382878'

Test #103:

score: 0
Accepted
time: 273ms
memory: 24184kb

input:

500000 500000 50
74126 49011 367514 417555 184560 286059 74126 231718 83481 202258 411813 347616 60325 74126 74126 286009 74126 74126 74126 179065 110803 74126 184833 288128 388123 74126 74126 93751 130398 74126 125311 74126 254881 188001 108766 74126 216739 458816 352692 74126 343092 138882 121669 ...

output:

388605

result:

ok single line: '388605'

Test #104:

score: 0
Accepted
time: 293ms
memory: 24420kb

input:

500000 500000 100
86461 233990 79316 421287 65269 35378 441920 218216 326582 53709 231648 104859 251907 368631 12230 233266 458846 413320 464580 185043 36534 217436 235896 147447 323269 298618 272107 239801 331774 260283 14204 18336 403456 164055 47288 189349 140395 104161 111609 230062 249582 18306...

output:

316118

result:

ok single line: '316118'

Test #105:

score: 0
Accepted
time: 290ms
memory: 24304kb

input:

500000 500000 500
317156 322156 494965 421755 316506 344062 215650 117107 404655 136839 99599 377713 398553 358220 3168 402743 331586 264497 5706 379089 319033 346013 455742 120914 307683 114651 488018 436234 328984 474109 83330 455465 235972 356020 221510 470760 239610 314596 184357 30639 196228 16...

output:

316612

result:

ok single line: '316612'

Test #106:

score: 0
Accepted
time: 314ms
memory: 24432kb

input:

500000 500000 1000
287769 200264 467626 249411 177383 185151 480172 472198 209378 152588 419930 77161 80980 324085 95712 372613 227499 171437 59676 455301 150774 343341 143003 471079 422787 405738 378512 46559 347993 26033 55537 15554 423367 83975 146233 499539 219755 499441 305607 323634 314176 163...

output:

316382

result:

ok single line: '316382'

Test #107:

score: 0
Accepted
time: 302ms
memory: 24432kb

input:

500000 500000 5000
29097 482850 493172 169301 202467 153142 227539 394320 212453 126183 494312 434921 113472 294417 49068 50040 117099 35577 334975 24810 143735 216300 183819 305311 74834 101949 483930 27899 305218 95181 141808 124670 436794 54792 77370 480662 289415 253008 331927 110733 421843 2300...

output:

321548

result:

ok single line: '321548'

Test #108:

score: 0
Accepted
time: 317ms
memory: 24520kb

input:

500000 500000 10000
181264 414513 299591 90889 484478 330192 456670 390993 265407 367415 240702 403742 125367 315829 339749 439053 84378 309169 27097 148214 213586 449787 131495 228870 459800 455486 363137 20027 131681 308879 330763 313249 250746 420732 189828 40677 86404 395099 151933 478070 329019...

output:

325541

result:

ok single line: '325541'

Test #109:

score: 0
Accepted
time: 319ms
memory: 24240kb

input:

500000 500000 50000
332309 215491 215960 231981 78455 328186 70704 450637 445050 324766 469231 91236 366432 28231 159093 340824 216846 105069 491756 346856 478182 369766 42554 45643 359690 299854 383952 110806 467626 165014 60686 232543 361469 256884 330511 302173 338156 27982 233329 181220 377621 3...

output:

365957

result:

ok single line: '365957'

Test #110:

score: 0
Accepted
time: 320ms
memory: 24208kb

input:

500000 500000 100000
494950 127600 382303 13426 440066 313670 207504 377956 215847 41089 14988 203503 209583 390784 56974 249208 319129 162872 486515 21875 342186 401112 118041 118838 220152 6811 119207 161317 309896 345143 486716 188324 319757 216954 199101 338856 112356 467088 321624 496324 185106...

output:

415982

result:

ok single line: '415982'

Test #111:

score: 0
Accepted
time: 308ms
memory: 24092kb

input:

500000 500000 200000
310623 2810 238332 28613 463369 281030 7469 449506 174193 177392 156716 322737 391015 38888 286455 472642 429013 417969 490763 490099 490274 243206 41347 10345 417854 277217 379127 266984 260017 491775 77844 335498 298576 459547 136692 436035 387640 183348 40646 262252 406862 41...

output:

500000

result:

ok single line: '500000'

Test #112:

score: 0
Accepted
time: 313ms
memory: 24084kb

input:

500000 500000 300000
11225 190808 109993 401458 92547 132952 494060 263513 385433 280477 414936 284138 157418 315242 341687 252431 452366 20277 390392 414971 189064 428131 203564 131674 26532 375958 285893 94697 165841 351875 448584 155119 131702 33144 38647 396581 447202 82975 282346 195774 448569 ...

output:

500000

result:

ok single line: '500000'

Test #113:

score: 0
Accepted
time: 302ms
memory: 24168kb

input:

500000 500000 400000
470436 376573 347828 215247 435425 456031 58404 72719 149823 209332 9004 344149 384307 459271 435967 291247 415776 482325 158474 112139 270538 138174 304635 81801 445927 202151 7915 180375 221732 394754 194478 128096 241859 308102 340664 278172 378122 141634 224143 433525 141235...

output:

500000

result:

ok single line: '500000'

Test #114:

score: 0
Accepted
time: 296ms
memory: 24376kb

input:

500000 500000 450000
38822 317526 140637 371106 231927 353625 151795 28745 455224 49153 22557 434600 393316 461444 429937 243418 452907 136150 276080 283550 20050 278231 366379 305960 39457 82367 488114 322659 53930 257842 166760 457335 94121 87705 440161 496248 131993 480880 255499 206748 7205 1077...

output:

500000

result:

ok single line: '500000'

Test #115:

score: 0
Accepted
time: 98ms
memory: 21548kb

input:

150000 500000 1
101965 274429 382411 408673 22540 393958 380692 273187 215479 234127 10279 356944 407842 295888 204835 68215 88522 13834 322600 212533 423448 294187 416110 130477 277030 253909 351400 48691 274960 154741 130303 389785 26581 431410 304003 319360 333289 332197 403822 396286 122179 2840...

output:

0

result:

ok single line: '0'

Test #116:

score: 0
Accepted
time: 106ms
memory: 22888kb

input:

166666 500000 1
356284 48118 151504 339301 176992 402955 322582 90106 64657 34384 337750 415720 197266 92893 83437 49210 19789 17638 246796 293395 148900 22822 164209 199939 367267 377767 94936 306787 375247 6829 147109 397063 23059 98926 446119 205837 30706 426847 406960 459949 335188 195187 479740...

output:

1

result:

ok single line: '1'

Test #117:

score: 0
Accepted
time: 241ms
memory: 9760kb

input:

500000 500000 499999
101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121 101121...

output:

500000

result:

ok single line: '500000'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%