QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563121#3243. 赛程制定ElegiaAC ✓11547ms32096kbC++234.3kb2024-09-14 02:54:102024-09-14 02:55:52

Judging History

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

  • [2024-09-14 02:55:52]
  • 评测
  • 测评结果:AC
  • 用时:11547ms
  • 内存:32096kb
  • [2024-09-14 02:54:10]
  • 提交

answer

//tnnd,怎么这么卡常
#include<bits/stdc++.h>
using namespace std;

int read(){
	int a = 0; char c = getchar(); while(!isdigit(c)) c = getchar();
	while(isdigit(c)){a = a * 10 + c - 48; c = getchar();} return a;
}

#define int long long
const int _ = 2e5 + 7 , __ = _ * 5; int N , A[_] , B[_] , C[_] , sum[3][_] , L1 , L2; vector < int > pot;
int findid(int x){return (--upper_bound(pot.begin() , pot.end() , x)) - pot.begin() + 1;}
struct segt{
#define lowbit(x) ((x) & -(x))
	signed sum[__] , rt; void clr(){memset(sum , 0 , sizeof(sum)); rt = 1;}
	void mdf(signed x , int l , int r , int t , int c = 1){while(t <= (int)pot.size() + 1){sum[t] += c; t += lowbit(t);}}
	int qry(int x , int l , int r , int L , int R){int all = 0; while(R){all += sum[R]; R -= lowbit(R);} return all;}
}Tree[3];

int Count(int mid){
	int num = 0 , mrk1 = 0 , mrk2 = 0;
	if(pot.empty()){
		for(int i = 1 ; i + L2 - 1 <= N ; ++i){
			pot.push_back(sum[0][i + L2 - 1] - sum[0][i - 1]);
			pot.push_back(sum[2][i + L2 - 1] - sum[2][i - 1]);
		}
		for(int i = L1 - L2 + 2 ; i <= L1 && i + L2 - 1 <= N ; ++i) pot.push_back(sum[2][L1] - sum[2][i - 1] + sum[0][i + L2 - 1] - sum[0][L1]);
		for(int i = 1 ; i + L1 - 1 <= N ; ++i){
			if(i + L1 + L2 - 1 <= N) pot.push_back(sum[0][i + L1 + L2 - 1] - sum[0][i + L1 - 1] - mrk2);
			mrk2 += C[i + L1] - 2 * B[i + L1]; pot.push_back(sum[2][i + L2 - 1] - sum[2][i - 1] - mrk1); mrk1 += 2 * B[i] - C[i];
		}
		sort(pot.begin() , pot.end()); pot.resize(unique(pot.begin() , pot.end()) - pot.begin());
	}
	
	mrk1 = mrk2 = 0; for(int i = 0 ; i < 3 ; ++i){Tree[i].clr();} 
	for(int i = 1 ; i <= L1 - L2 + 1 ; ++i) Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[2][i + L2 - 1] - sum[2][i - 1]));
	for(int i = L1 - L2 + 2 ; i <= L1 && i + L2 - 1 <= N ; ++i) Tree[2].mdf(Tree[2].rt , 0 , pot.size() + 1 , findid(sum[2][L1] - sum[2][i - 1] + sum[0][i + L2 - 1] - sum[0][L1]));
	for(int i = L1 + 1 ; i + L2 - 1 <= N ; ++i) Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[0][i + L2 - 1] - sum[0][i - 1]));
	for(int i = 1 ; i + L1 - 1 <= N ; ++i){
		num += Tree[0].qry(Tree[0].rt , 0 , pot.size() + 1 , 0 , findid(mid - sum[0][i + L1 - 1] + sum[0][i - 1])) +
			Tree[1].qry(Tree[1].rt , 0 , pot.size() + 1 , 0 , findid(mid - mrk1 - sum[0][i + L1 - 1] + sum[0][i - 1])) +
			Tree[2].qry(Tree[2].rt , 0 , pot.size() + 1 , 0 , findid(mid - mrk2 - sum[0][i + L1 - 1] + sum[0][i - 1]));
		if(i + L1 - 1 == N) continue;
		if(i + L1 + L2 - 1 <= N){
			Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[0][i + L1 + L2 - 1] - sum[0][i + L1 - 1]) , -1);
			Tree[2].mdf(Tree[2].rt , 0 , pot.size() + 1 , findid(sum[0][i + L1 + L2 - 1] - sum[0][i + L1 - 1] - mrk2));
		}
		mrk2 += C[i + L1] - 2 * B[i + L1];
		Tree[2].mdf(Tree[2].rt , 0 , pot.size() + 1 , findid(sum[2][i + L1] - sum[2][i + L1 - L2] - mrk2) , -1);
		Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[2][i + L1] - sum[2][i + L1 - L2]));
		Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[2][i + L2 - 1] - sum[2][i - 1]) , -1);
		Tree[1].mdf(Tree[1].rt , 0 , pot.size() + 1 , findid(sum[2][i + L2 - 1] - sum[2][i - 1] - mrk1));
		mrk1 += 2 * B[i] - C[i];
		if(i >= L2){
			Tree[1].mdf(Tree[1].rt , 0 , pot.size() + 1 , findid(sum[0][i] - sum[0][i - L2] - mrk1) , -1);
			Tree[0].mdf(Tree[0].rt , 0 , pot.size() + 1 , findid(sum[0][i] - sum[0][i - L2]));
		}
	}
	return num;
}

int check(int val , int L = 1 , int R = 2e14){
	while(L < R){
		int mid = (L + R) >> 1;
		Count(mid) >= val ? R = mid : L = mid + 1;
	} return L;}
double check1(int val){
	int L = 1 , R = 2e14;
	while(L < R){
		int mid = (L + R) >> 1 , C = Count(mid);
		if(C >= val + 1) R = mid; else if(C < val) L = mid + 1;
		else{int p = check(val , L , mid), q = check(val + 1 , mid + 1 , R); return (p + q) * 0.5;}
	}
	return L;
}

signed main(){
	N = read(); L1 = read(); L2 = read(); for(int i = 1 ; i <= N ; ++i){A[i] = read(); B[i] = read(); C[i] = read();}
	L1 = min(N, L1); L2 = min(N, L2); if(L1 < L2) swap(L1 , L2); int all = 0; for(int i = 1 ; i <= N ; ++i){all += A[i]; B[i] -= A[i]; C[i] -= A[i];} 
	for(int i = 1 ; i <= N ; ++i){sum[0][i] = sum[0][i - 1] + B[i]; sum[1][i] = sum[1][i - 1] + C[i]; sum[2][i] = sum[1][i] - sum[0][i];}
	int num = Count(1e15); if(num & 1) cout << check(num / 2 + 1) + all << ".0"; else cout << fixed << setprecision(1) << check1(num / 2) + all;
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 11547ms
memory: 31604kb

input:

199999 1313 1574
875341 70037940 545658979
408151922 593127952 896204843
398572860 713355508 782341229
385480539 445158673 542359269
38390184 493302262 829553979
288821162 631929986 848858906
506082300 705337673 881503149
446625212 739665436 783314314
200291546 272742805 600433078
6016361 224581494 ...

output:

42379459554063.5

result:

ok single line: '42379459554063.5'

Test #2:

score: 0
Accepted
time: 11178ms
memory: 31288kb

input:

200000 1313 1574
12239133 67611206 300250319
213917778 665821502 832693160
465441005 683667397 891487977
196242478 842759648 888257923
46002084 250519215 472059099
396357947 600930512 735440534
747096355 954988804 959749032
287860913 578379412 729290957
100629004 333731901 505159512
13374856 4213569...

output:

42259999970866.0

result:

ok single line: '42259999970866.0'

Test #3:

score: 0
Accepted
time: 2420ms
memory: 27576kb

input:

200000 100000 100000
269828723 638351072 677430413
280830698 302829417 991764744
159386767 500427626 502914795
210055599 292101771 784161795
103783986 442735272 747588966
263327571 302151891 598407882
84670406 97490683 326066076
368143525 484933503 758995786
3660655 329354013 766429052
126226277 239...

output:

62208658783473.0

result:

ok single line: '62208658783473.0'

Test #4:

score: 0
Accepted
time: 44ms
memory: 24784kb

input:

199999 199999 200000
333975446 852491304 910509471
52456304 202780333 344861221
5412194 695862007 803764302
107492905 304729272 786968045
109207800 327132509 335209768
107474432 117660278 840101186
78251277 308806044 312181160
685081388 843082546 960526372
46284915 96190452 123502819
577656124 63910...

output:

146335558335621.0

result:

ok single line: '146335558335621.0'

Test #5:

score: 0
Accepted
time: 20ms
memory: 21972kb

input:

12 347 401
42697205 664528904 717034022
45186321 570608894 621164850
65920233 159527364 208249293
18964832 616799612 653876249
39424360 378605590 384012456
69045497 89095607 109702179
67536374 159829756 253932492
12275097 465131236 505070514
44734459 772057700 789182922
55361998 191262075 240115263
...

output:

5576509252.0

result:

ok single line: '5576509252.0'

Test #6:

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

input:

456 464 391
23017985 204918116 640620553
75034595 175898023 599159336
71329799 364759887 693840457
85122380 270419886 389594437
51494864 446198582 488461996
693910 358513360 774118953
7715081 331232310 507891876
17011471 220085106 298388061
51359591 391929535 635012751
99859586 196277989 586737740
7...

output:

205949860645.0

result:

ok single line: '205949860645.0'

Test #7:

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

input:

427 32 453
142650466 640243289 665459330
114445846 602330505 714585561
26842677 255146273 388966855
114585710 578689901 757728483
161340543 312978021 364208664
132016451 206670135 282477973
166744625 265296484 292471635
17115153 478721950 617023641
170385101 602155804 762137004
116958117 696498822 7...

output:

155788721241.0

result:

ok single line: '155788721241.0'

Test #8:

score: 0
Accepted
time: 29ms
memory: 22644kb

input:

394 352 151
173776248 258411483 369102088
181540318 254982276 514029554
114197153 147363850 288820421
10494442 123523195 300023188
131290662 319334098 560642647
94302894 202948181 690687444
156269206 275024819 718542470
65107873 204481942 663223459
73352852 239220952 802679869
76272474 270952704 530...

output:

109651554871.0

result:

ok single line: '109651554871.0'

Test #9:

score: 0
Accepted
time: 28ms
memory: 22820kb

input:

358 192 253
290104388 306840810 398934172
150125368 207726230 271396978
207167819 241445386 293401155
599106751 731210712 816576855
161377987 244106877 282894952
13844183 199863848 224907238
123706937 181577252 233653567
134764224 192463451 232053115
33971899 103092212 130415940
225188001 240799572 ...

output:

143459931871.0

result:

ok single line: '143459931871.0'

Test #10:

score: 0
Accepted
time: 23ms
memory: 20952kb

input:

326 12 220
94971994 298718059 450027809
117252608 260378001 470873740
294522295 533695731 593287489
295048250 376076773 458937094
131328106 150495722 405685415
176130626 222400070 359374886
86940574 165014643 333433458
82756945 218223444 478285701
10648706 213899185 418475222
158244182 189028046 271...

output:

76765509992.0

result:

ok single line: '76765509992.0'

Test #11:

score: 0
Accepted
time: 20ms
memory: 22636kb

input:

299 328 378
55660294 303814867 548742796
81431455 213042009 380958418
44418983 48476333 383686719
58033412 147717975 552812180
7294754 51309275 134322752
50231090 143693816 515465408
68056969 302287487 729071259
61164229 62089653 74258676
72022920 297319343 784697215
59385063 341306774 512684640
856...

output:

126825085707.0

result:

ok single line: '126825085707.0'

Test #12:

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

input:

100000 200000 200000
25127503 43397412 101361955
26462453 213432039 476140462
326402540 424554643 862888635
131967241 133618801 258176572
44883021 108743797 109580638
149816843 211080148 278509022
558212775 733036933 941082555
35778441 150704067 226389629
6864019 125667977 125801172
285845006 717175...

output:

49109131282197.0

result:

ok single line: '49109131282197.0'

Test #13:

score: 0
Accepted
time: 20ms
memory: 22552kb

input:

250 442 60
39219879 204776214 241045077
55847753 165794256 190786295
412337993 423722762 507241659
38751037 201855211 240045212
99123611 387167102 418492061
119951699 390643621 480246816
26052897 227459958 278790249
370024222 661407915 691091205
363312690 489771594 556107865
172065655 176696654 2358...

output:

98208363736.0

result:

ok single line: '98208363736.0'

Test #14:

score: 0
Accepted
time: 1817ms
memory: 27472kb

input:

200000 150000 50000
194726404 361749753 373569971
39608890 526512700 589435639
750195 143128496 234597273
153867242 156899157 435556396
210778063 614130759 851488812
194839427 232885638 377739907
226316238 420332859 456410817
53204154 152704111 185673866
361387206 570058932 950058790
55513682 116249...

output:

61522695804193.0

result:

ok single line: '61522695804193.0'

Test #15:

score: 0
Accepted
time: 1832ms
memory: 28088kb

input:

200000 50000 150000
138404089 205512986 450578845
321162553 552890375 666774020
60143255 107898116 518679867
258357095 492899014 836184929
6414374 32372147 117131410
427089 119348538 217144561
184902768 574986647 690915741
140917300 150587798 245868627
239327980 243156837 928797678
158372462 3207209...

output:

61699752126422.0

result:

ok single line: '61699752126422.0'

Test #16:

score: 0
Accepted
time: 6043ms
memory: 30436kb

input:

199999 31548 71733
6958787 48322896 126312414
247006173 378444261 617180007
111126091 174486969 240744057
5131653 138173179 276994397
51698831 93636503 107051414
161061302 298988051 641981340
85278378 246019297 530475972
85625352 214749542 270970650
42780894 47439935 133550361
182887650 195948148 82...

output:

44888884665610.0

result:

ok single line: '44888884665610.0'

Test #17:

score: 0
Accepted
time: 10917ms
memory: 32096kb

input:

199997 1 1
101568166 125814958 463512042
28573582 83224619 122536556
34024856 137526974 250903028
75663745 284114795 578656886
160968160 302523296 934780050
78026537 80889726 130763867
8941327 89066110 251907103
193977168 427716349 725263212
15394882 165608172 223084494
147900823 421126361 623385073...

output:

28007367679175.0

result:

ok single line: '28007367679175.0'

Test #18:

score: 0
Accepted
time: 9015ms
memory: 30516kb

input:

171902 31318 3
31591116 65830961 103673326
42141421 152721445 737307055
235043789 371978101 871701487
25047193 188619012 734842756
134181674 142572587 684798594
161146757 255517845 808947929
7172417 273438598 828948967
126007470 387409778 413328159
138145019 157803192 256263070
365765362 399320915 7...

output:

43815595258337.0

result:

ok single line: '43815595258337.0'

Test #19:

score: 0
Accepted
time: 11175ms
memory: 30928kb

input:

199999 1 1
107870253 685817562 845011845
211617730 733321508 923205936
27864743 181255732 450456657
47415390 665961242 791461636
40783036 459675326 607251831
311278964 462500396 500869119
221289918 603042864 744518049
87781385 448321728 803396901
4587338 686900801 931181476
45747658 530354503 848992...

output:

41772229089363.0

result:

ok single line: '41772229089363.0'

Test #20:

score: 0
Accepted
time: 7370ms
memory: 29988kb

input:

171651 51409 3
107732573 667215395 893082074
277346219 417627448 484108810
248042995 585193196 736305560
315999878 332568685 369825741
188642087 473228943 966792440
946835630 950910993 961623259
164930017 527076188 790323237
41034390 52438349 109288952
40375897 74700886 953394704
16574721 18469473 1...

output:

48891448162570.0

result:

ok single line: '48891448162570.0'