QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563121 | #3243. 赛程制定 | Elegia | AC ✓ | 11547ms | 32096kb | C++23 | 4.3kb | 2024-09-14 02:54:10 | 2024-09-14 02:55:52 |
Judging History
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'