QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#625281#6104. Building BombingDreamAwakingAC ✓275ms31520kbC++142.8kb2024-10-09 18:23:282024-10-09 18:23:28

Judging History

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

  • [2024-10-09 18:23:28]
  • 评测
  • 测评结果:AC
  • 用时:275ms
  • 内存:31520kb
  • [2024-10-09 18:23:28]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
const int maxn=1e5+5;
int nums[maxn],rk[maxn];
const int N=1e5+5;
struct seg{
	int val[N<<2],lazy[N<<2];    //树和懒标记
	void pushup(int p){
		//更新信息,实际情况中需要修改
		val[p]=min(val[ls],val[rs]);
	}
	//懒标记下推 
	void pushdown(int p,int l,int r,int mid){
		//如果有懒标记 
		if(lazy[p]){
			//下面代码根据实际情况修改
			//修改左右孩子的懒标记和值
			lazy[ls]+=lazy[p];
			lazy[rs]+=lazy[p];
			val[ls]+=lazy[p];
			val[rs]+=lazy[p]; 
			lazy[p]=0;
		} 
	}
	void build(int p,int l,int r){
		//build(1,1,范围最大值)
		val[p]=1e9+5;
		if(l==r){
			val[l]=1e9+5;
			return;
		}
		int mid=l+r>>1;	
		build(ls,l,mid);
		build(rs,mid+1,r);
		pushup(p);
	}
    //区间加上某个值
	void update(int p,int l,int r,int st,int en,int vval){
		//[l,r]表示当前区间,[st,en]表示需要修改的区间,vval表示修改元素的变化量
		if(st<=l&&en>=r){
			//可修改,处理val和懒标记
			val[p]+=vval;
			lazy[p]+=vval; 
			return;
		} 
		//否则懒标记下放
		int mid=l+r>>1;
		pushdown(p,l,r,mid);
		//能放进来说明[st,en]和[l,r]有交集 
		if(st<=mid)update(ls,l,mid,st,en,vval);
		if(en>mid)update(rs,mid+1,r,st,en,vval);
		pushup(p); 
	}
	int query(int p,int l,int r,int st,int en){
		//统计
		//如果全合法
		if(st<=l&&en>=r)return val[p];
		//否则递归寻找合法区间,并且要将懒标记下放 
		int mid=l+r>>1;
		pushdown(p,l,r,mid);
		int ans=1e9+10;
		if(st<=mid)ans=min(ans,query(ls,l,mid,st,en));
		if(en>mid)ans=min(ans,query(rs,mid+1,r,st,en));
		return ans; 
	}	 
}T[11];
//需要维护和查询区间最小值
void slove(){
	int n,l,z;
	cin>>n>>l>>z;
	for(int i=1;i<=n;i++)cin>>nums[i];

	//离散化
	for(int i=1;i<=n;i++)rk[i]=nums[i];
	sort(rk+1,rk+n+1);
	int m=unique(rk+1,rk+n+1)-rk-1;
	for(int i=1;i<=n;i++)nums[i]=lower_bound(rk+1,rk+m+1,nums[i])-rk;

	//建树
	for(int k=1;k<=z;k++)T[k].build(1,1,m);
	T[1].update(1,1,m,nums[l],nums[l],-1e9-5);
	
	//dp+线段树维护
	for(int i=l+1;i<=n;i++){
		if(nums[i]==1)continue;
			for(int k=z;k>=1;k--){
					T[k].update(1,1,m,1,nums[i]-1,1);
					if(k>1){
						int tmp=T[k-1].query(1,1,m,1,nums[i]-1);
						int ttmp=T[k].query(1,1,m,nums[i],nums[i]);
						if(tmp<ttmp){
							T[k].update(1,1,m,nums[i],nums[i],-ttmp);
							T[k].update(1,1,m,nums[i],nums[i],tmp);
						}
					}
			}
	}
	int ans=T[z].query(1,1,m,1,m);
	if(ans>=n){
		cout<<-1<<endl;
		return;
	}
	for(int i=1;i<l;i++){
		if(nums[i]>=nums[l])ans++;
	}
	cout<<ans<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t=1;
	//cin>>t;
	while(t--)slove();
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9744kb

input:

7 2 3
10 30 90 40 60 60 80

output:

2

result:

ok 1 number(s): "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7728kb

input:

3 2 2
30 20 10

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7700kb

input:

1 1 1
608954134

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9832kb

input:

10 5 3
872218248 517822599 163987167 517822599 458534407 142556631 142556631 458534407 458534407 872218248

output:

-1

result:

ok 1 number(s): "-1"

Test #5:

score: 0
Accepted
time: 1ms
memory: 7780kb

input:

10 4 2
31201623 546478688 709777934 672927273 672927273 709777934 801718395 672927273 926114576 38983342

output:

3

result:

ok 1 number(s): "3"

Test #6:

score: 0
Accepted
time: 1ms
memory: 9716kb

input:

10 2 3
376738377 852081435 10550876 40942086 10550876 10550876 697114820 40942086 473788030 10550876

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 1ms
memory: 7776kb

input:

10 1 2
216184450 216184450 488086371 73015591 802501830 860488380 488086371 643751501 979419002 860488380

output:

3

result:

ok 1 number(s): "3"

Test #8:

score: 0
Accepted
time: 0ms
memory: 15900kb

input:

10 4 5
81167617 293949746 274292711 760663226 760663226 373523484 261723185 760663226 261723185 713804678

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

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

input:

10 1 10
8775290 171732800 240074429 560150106 594414689 615008126 693779505 808555946 960743397 991906871

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 26184kb

input:

10 3 10
756674120 838411846 543989864 756674120 513122553 460005403 513122553 985890594 985890594 985890594

output:

-1

result:

ok 1 number(s): "-1"

Test #11:

score: 0
Accepted
time: 1ms
memory: 7768kb

input:

1 1 2
270411237

output:

-1

result:

ok 1 number(s): "-1"

Test #12:

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

input:

1 1 10
526049243

output:

-1

result:

ok 1 number(s): "-1"

Test #13:

score: 0
Accepted
time: 4ms
memory: 24228kb

input:

9 1 10
264254461 350329437 354458165 361860512 455656110 705176463 823349533 901851526 968433321

output:

-1

result:

ok 1 number(s): "-1"

Test #14:

score: 0
Accepted
time: 7ms
memory: 24912kb

input:

100000 96719 10
364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 364310492 3643...

output:

-1

result:

ok 1 number(s): "-1"

Test #15:

score: 0
Accepted
time: 156ms
memory: 17704kb

input:

100000 2497 5
343693559 278257334 676244785 747854142 264361825 95333041 776651570 594011112 873418698 621428434 786267296 768933320 42014826 78577061 184127759 609382698 742865448 244899891 900674947 239300558 403763537 971259502 527902246 463159146 534953311 681716687 25155119 381556831 892857155 ...

output:

2368

result:

ok 1 number(s): "2368"

Test #16:

score: 0
Accepted
time: 37ms
memory: 27428kb

input:

100000 92400 8
868958568 811740770 68445106 478059498 416417069 21575964 450624368 808476181 342985254 360591658 646117800 592265888 973799101 964009069 226577201 51499379 892758433 666404354 455887531 525819830 939131873 923403705 336093706 11560544 887737943 162368659 379520302 113187738 458771468...

output:

40990

result:

ok 1 number(s): "40990"

Test #17:

score: 0
Accepted
time: 242ms
memory: 24968kb

input:

100000 1 8
695671626 848651400 604068730 459348208 791555592 75324203 270656574 786976169 551782202 989733359 621670958 873203369 660794091 26636715 211845471 274824833 388484655 452241033 620810130 773154683 485379577 350366864 604367460 692171223 931744202 116105771 118804410 60531672 751732850 91...

output:

3

result:

ok 1 number(s): "3"

Test #18:

score: 0
Accepted
time: 4ms
memory: 16480kb

input:

100000 80143 5
958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 958091046 95809...

output:

-1

result:

ok 1 number(s): "-1"

Test #19:

score: 0
Accepted
time: 57ms
memory: 31520kb

input:

100000 85921 9
844534796 487284545 877589803 529990478 580018694 981656100 702150558 229913663 698180684 401544329 756257123 834768806 31825212 758757529 848447003 245375689 523530240 988937447 17456294 523532110 766526906 286157416 107207126 608575468 11728927 115685982 521238285 618582131 59680810...

output:

35095

result:

ok 1 number(s): "35095"

Test #20:

score: 0
Accepted
time: 237ms
memory: 26640kb

input:

100000 8528 8
853411256 116828037 724833572 436072994 234224812 981688025 243985329 725855530 822986729 321625686 903720699 620740073 316282968 836252277 403239274 374974032 788273938 549976382 620756572 65712332 576978656 301979594 381661885 42430558 594472122 202954950 695312140 727865575 89554406...

output:

4079

result:

ok 1 number(s): "4079"

Test #21:

score: 0
Accepted
time: 83ms
memory: 11224kb

input:

100000 1 2
14842275 624960832 939005094 182912868 247722361 586288392 560379602 997318995 223958340 907383048 448898932 624124016 161712527 531109265 415852790 621012665 715042136 679130521 699505725 761012196 19037128 300827216 306053333 32340676 533716096 30787143 181005831 550740185 209929952 784...

output:

255

result:

ok 1 number(s): "255"

Test #22:

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

input:

100000 63567 9
107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 107161200 10716...

output:

-1

result:

ok 1 number(s): "-1"

Test #23:

score: 0
Accepted
time: 59ms
memory: 16728kb

input:

100000 69346 4
205462056 194873942 308283742 799844503 254589910 620254212 675271726 200222667 895280483 515014103 86587801 673015913 322285177 285134540 714948924 966076416 352455814 395122031 682049959 460865577 308323775 264208873 318695573 168047985 464754659 42635053 615814610 775704705 2134637...

output:

61684

result:

ok 1 number(s): "61684"

Test #24:

score: 0
Accepted
time: 34ms
memory: 15704kb

input:

100000 91952 4
586693219 734754252 335593389 760459654 30320500 357889182 215432363 186047722 836305413 574424762 478700099 906404117 125434605 466615323 951690126 476806776 872165646 904301769 343543494 52962234 314018380 863324661 720882170 918598963 711966391 108101017 492623819 416555808 7864903...

output:

74291

result:

ok 1 number(s): "74291"

Test #25:

score: 0
Accepted
time: 78ms
memory: 10532kb

input:

100000 1 2
339072634 993056221 389320016 512367300 446857121 855973410 485642657 910649280 261247499 987665465 184881410 571095682 851601711 132090797 18041297 946819243 197092133 760038514 682125668 763723510 676353244 312454998 29094899 985581709 942882817 861329610 668112676 741933446 488279249 9...

output:

192

result:

ok 1 number(s): "192"

Test #26:

score: 0
Accepted
time: 6ms
memory: 10524kb

input:

100000 79695 3
700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 700941753 70094...

output:

-1

result:

ok 1 number(s): "-1"

Test #27:

score: 0
Accepted
time: 65ms
memory: 13680kb

input:

100000 52770 4
76631219 734778826 48091074 755914769 197289467 971620458 690621326 713580629 222366003 17765400 708350289 439930172 857198928 394710629 905141414 982205433 70371450 334803238 349296055 273107173 917358160 518005467 905060152 368248444 301852180 828256335 205647338 154488564 810301495...

output:

3776

result:

ok 1 number(s): "3776"

Test #28:

score: 0
Accepted
time: 91ms
memory: 30056kb

input:

100000 75376 9
643499650 354538725 53375286 291978452 803331448 756507906 730160267 268730254 689030079 949417829 396081561 699120144 323676858 6551351 789922321 310304779 196941465 192025305 995490671 632974995 5576251 599315 127021495 614354532 415048508 282448145 562686759 573145730 118489496 325...

output:

44020

result:

ok 1 number(s): "44020"

Test #29:

score: 0
Accepted
time: 226ms
memory: 20756kb

input:

100000 1 7
523380019 15333995 493673852 767485542 193049213 167068941 657090882 349342432 985356056 14022614 216663009 35706172 204550655 223775913 671622634 377925440 27146297 443005872 362021013 360480148 891142361 833434539 734935257 298107282 11856717 526039416 710163988 356691347 465954461 1751...

output:

7

result:

ok 1 number(s): "7"

Test #30:

score: 0
Accepted
time: 7ms
memory: 22384kb

input:

100000 63119 8
439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 439946499 43994...

output:

-1

result:

ok 1 number(s): "-1"

Test #31:

score: 0
Accepted
time: 80ms
memory: 18288kb

input:

100000 68898 6
799856832 440773587 876530418 416225483 275373534 783819171 618331878 669353125 56132113 554981067 794588882 892917968 158389890 619144498 422676412 958497073 169121781 904236147 703839789 565695117 364430932 441711009 773409884 155270320 627374842 784122699 521523562 80451077 3337120...

output:

65818

result:

ok 1 number(s): "65818"

Test #32:

score: 0
Accepted
time: 151ms
memory: 26928kb

input:

100000 58800 9
515619297 895567406 955059302 604994146 794400525 869338846 710807572 174142554 536391573 315484679 226768398 259143881 770640770 809907282 324442535 692590954 84265792 75288514 460441964 463786466 516850385 789297367 842627409 107799913 210041825 449598630 197364675 147519520 7833731...

output:

38590

result:

ok 1 number(s): "38590"

Test #33:

score: 0
Accepted
time: 275ms
memory: 30108kb

input:

100000 1 9
967448444 901752045 327358565 417651777 511574999 243034146 626958995 862405853 234823444 512013730 105383999 943651806 489920114 66103117 619536192 87715369 320834248 862032596 699280002 424099363 245442371 644307438 395406206 821792808 450997527 785545319 875287467 871351742 555143873 7...

output:

3

result:

ok 1 number(s): "3"

Test #34:

score: 0
Accepted
time: 26ms
memory: 24948kb

input:

100000 1 10
158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 158606431 15860643...

output:

-1

result:

ok 1 number(s): "-1"

Test #35:

score: 0
Accepted
time: 22ms
memory: 24960kb

input:

100000 1 10
7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 7663300 ...

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 27ms
memory: 26928kb

input:

100000 1 10
32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 32565777 ...

output:

16523

result:

ok 1 number(s): "16523"

Test #37:

score: 0
Accepted
time: 83ms
memory: 24940kb

input:

100000 1 10
515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 515632 5...

output:

95042

result:

ok 1 number(s): "95042"

Test #38:

score: 0
Accepted
time: 38ms
memory: 9128kb

input:

100000 1 1
6944 602102863 428581297 635961043 517042686 930742857 511459974 548233271 310676710 438997140 406491162 16443055 641114107 416028240 193442056 675851036 34331752 381769277 52514351 312369730 193008608 737428803 393525554 285495112 47849751 961938154 412787449 129068602 717850694 81044118...

output:

99999

result:

ok 1 number(s): "99999"

Test #39:

score: 0
Accepted
time: 30ms
memory: 8608kb

input:

100000 50000 1
935860805 985130033 782895781 739086796 859970843 504969873 982451813 339193953 830829630 960098998 479744296 32119815 336992875 584329585 21227100 413370515 253619426 879496633 736806966 888735291 778873833 229331239 929308203 742474269 799800137 23697530 170099575 333815481 55900334...

output:

99999

result:

ok 1 number(s): "99999"

Test #40:

score: 0
Accepted
time: 22ms
memory: 7844kb

input:

100000 100000 1
38413036 456923902 821971466 586909482 636298728 158178471 84422915 632002470 34405999 882453211 922025994 294603996 207311349 526030511 417456448 362917277 456078308 435018316 47342069 47738636 642863127 189926256 40263985 58857249 119358305 864464366 83617839 485428518 305918980 94...

output:

99999

result:

ok 1 number(s): "99999"

Test #41:

score: 0
Accepted
time: 21ms
memory: 7920kb

input:

100000 100000 1
689062 162496087 815635790 86454103 919153712 600232358 34533362 470003401 945478254 712042501 567072009 609294130 765415123 322184738 412574796 341159622 509450206 788431438 57233122 145681970 584871000 919312099 981955631 137363227 678722976 74617074 898156030 118105366 422471343 1...

output:

22895

result:

ok 1 number(s): "22895"

Test #42:

score: 0
Accepted
time: 22ms
memory: 8608kb

input:

100000 100000 2
204648826 519310181 158466005 593656140 188707463 805777322 562522504 351061484 83797607 949142506 766717762 114129241 298963284 570186890 650249982 506221787 558807773 537012748 174235485 946242670 484547037 112843050 762578630 254962251 308746175 295258411 630134089 160349970 14394...

output:

-1

result:

ok 1 number(s): "-1"