QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130240 | #5258. Mortgage | stefanbalaz2222 | TL | 2666ms | 56932kb | C++14 | 2.6kb | 2023-07-23 18:44:50 | 2023-07-23 18:44:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<int,int> pii;
int mod=1000000+7;
const double dmod=(double)1/mod;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=2e5+10;
ll p[maxn],a[maxn],inf=1e18;
int n,q;
struct line{
ll a,b;
ll eval(ll x){
return a*x+b;
}
};
vector<line> tree[maxn*4];
double intersect(line c1,line c2){
return ((double)c2.b-c1.b)/((double)c1.a-c2.a);
}
void append(vector<line>&v,line c){
while(v.size() && intersect(v.back(),c)<0)v.pop_back();
while(v.size()>=2 && intersect(v[v.size()-2],v[v.size()-1])>=intersect(v[v.size()-2],c))v.pop_back();
v.pb(c);
}
void build(int x,int l,int r){
for(int i=l;i<=r;i++){
line c;
c.a=-i;
c.b=p[i];
append(tree[x],c);
}
if(l==r)return;
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
}
ll go(vector<line>&v,ll x){
int l=0;
int r=v.size()-1;
int sr,ret=-1;
while(l<=r){
sr=(l+r)/2;
ll inter=inf;
if(sr<v.size()-1)inter=intersect(v[sr],v[sr+1]);
if(x<=inter){
r=sr-1;
ret=sr;
}
else l=sr+1;
}
return v[ret].eval(x);
}
ll qry(int x,int l,int r,int lp,int rp,ll val){
if(l>rp || r<lp)return inf;
if(l>=lp && r<=rp){
return go(tree[x],val);
}
int mid=(l+r)/2;
return min(qry(x*2,l,mid,lp,rp,val),qry(x*2+1,mid+1,r,lp,rp,val));
}
int main() {
//freopen("test.txt","r",stdin);
//freopen("moj.txt","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
p[i]=p[i-1]+a[i];
}
build(1,1,n);
while(q--){
int lp,rp;
scanf("%d %d",&lp,&rp);
rp=lp+rp-1;
ll l=0;
ll r=1e9;
ll x=-1;
ll sr;
while(l<=r){
sr=(l+r)/2;
ll pom=qry(1,1,n,lp,rp,sr);
if(pom-p[lp-1]+(lp-1)*sr>=0){
l=sr+1;
x=sr;
}
else r=sr-1;
}
if(x<0)printf("stay with parents\n");
else printf("%lld\n",x);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 24420kb
input:
10 10 21 18 19 18 16 15 13 13 13 10 10 1 6 4 7 3 2 2 6 5 2 6 3 2 4 1 1 5 6 3
output:
10 13 13 18 12 16 18 18 18 13
result:
ok 10 lines
Test #2:
score: 0
Accepted
time: 4ms
memory: 24440kb
input:
1000 1000 196 207 195 207 200 203 202 204 205 191 190 188 203 198 201 188 203 198 196 196 200 195 200 206 193 198 186 196 200 185 202 195 203 199 185 199 202 191 184 194 195 194 193 195 184 197 189 193 186 187 193 193 196 186 195 193 186 192 188 188 187 197 179 188 195 196 197 186 194 183 189 185 19...
output:
158 16 110 64 160 118 169 63 172 128 93 82 118 119 86 32 174 145 139 84 149 120 133 155 108 110 65 178 90 99 118 91 133 85 151 76 130 50 91 99 95 78 110 87 119 141 68 81 172 82 112 139 136 81 79 16 51 31 104 116 108 38 75 176 156 55 165 112 146 74 68 172 112 157 94 177 111 166 110 112 98 155 109 155...
result:
ok 1000 lines
Test #3:
score: 0
Accepted
time: 9ms
memory: 22828kb
input:
1000 1000 1023 912 1076 907 1015 1078 1075 1031 930 925 925 960 1013 893 1052 920 967 1046 960 1077 888 883 1045 1049 1034 1062 967 1021 986 938 871 916 901 1032 1003 1020 900 909 920 1048 884 859 1016 922 945 955 1002 1033 947 1025 970 862 929 908 912 956 873 845 933 873 921 918 904 884 1033 900 99...
output:
220 651 401 454 516 692 597 294 779 418 468 679 293 348 920 172 554 303 282 104 580 824 569 376 221 226 454 232 794 469 788 925 394 308 245 624 614 422 252 407 149 529 178 612 584 429 629 357 477 886 896 517 114 762 560 546 516 735 275 818 304 608 214 685 205 561 470 826 844 335 618 327 651 799 843 ...
result:
ok 1000 lines
Test #4:
score: 0
Accepted
time: 5ms
memory: 23868kb
input:
1000 1000 938 360 206 545 664 694 717 653 217 681 574 932 125 191 677 87 875 177 253 29 748 915 222 288 771 785 233 112 922 847 473 267 365 610 76 404 776 3 821 971 730 988 652 263 525 233 91 821 319 876 467 617 271 899 53 650 874 369 746 307 592 915 309 93 387 885 800 387 617 382 928 963 540 943 22...
output:
335 9 125 426 415 352 362 292 456 475 399 477 341 387 500 475 201 483 246 509 280 496 407 433 470 445 340 459 472 439 472 411 458 327 227 428 207 363 77 267 231 204 333 387 137 315 23 33 471 313 37 202 31 177 425 125 403 177 371 480 329 468 163 340 416 458 202 202 143 345 478 17 383 375 493 213 382 ...
result:
ok 1000 lines
Test #5:
score: 0
Accepted
time: 4ms
memory: 22784kb
input:
1000 1000 45 -80 65 -47 -17 75 49 79 38 65 25 64 53 74 0 -43 38 22 -48 -6 37 12 24 -36 -9 9 -64 -66 -31 91 -5 29 62 98 56 133 64 59 93 -6 97 89 7 121 125 21 39 95 131 60 -33 -4 6 63 52 44 25 -38 24 -40 94 135 129 129 13 87 28 -10 -13 168 128 140 1 152 52 88 99 107 88 81 176 18 73 29 93 165 50 146 13...
output:
419 136 345 312 338 1 490 557 177 84 50 688 315 784 141 244 stay with parents 53 408 218 764 451 127 371 823 805 349 552 167 523 stay with parents 500 3 52 411 51 699 422 435 278 187 134 252 585 108 583 44 55 109 310 167 879 712 stay with parents 336 311 108 stay with parents 51 434 stay with parent...
result:
ok 1000 lines
Test #6:
score: 0
Accepted
time: 9ms
memory: 24412kb
input:
1000 1000 210 201 195 208 191 209 201 195 201 192 199 200 205 188 200 198 197 207 189 199 194 197 206 186 198 204 203 187 200 201 197 197 191 197 192 191 192 188 189 194 197 191 192 182 184 195 192 183 200 193 193 193 192 190 190 194 182 197 180 191 184 181 189 184 186 180 194 197 194 187 196 196 18...
output:
92 92 102 93 89 114 149 105 72 114 87 71 77 171 90 36 127 136 39 165 92 62 157 135 101 82 87 78 136 99 141 73 109 141 23 73 76 112 58 110 105 97 84 181 19 100 127 76 108 109 49 150 165 159 152 101 108 94 25 87 67 78 127 56 37 50 161 131 142 40 47 73 117 169 87 157 109 121 59 75 184 80 67 82 48 61 65...
result:
ok 1000 lines
Test #7:
score: 0
Accepted
time: 9ms
memory: 24040kb
input:
1000 1000 1000 998 998 998 997 994 994 992 991 991 991 989 987 987 987 986 984 983 982 982 981 979 978 976 975 974 973 972 973 971 969 968 968 968 965 964 963 963 963 960 961 959 957 958 956 955 955 952 951 951 950 949 950 948 947 947 945 943 944 942 940 940 940 938 938 936 936 935 932 932 930 931 9...
output:
598 365 299 422 294 499 645 316 469 475 612 702 612 344 324 424 597 418 241 488 471 618 640 946 673 350 728 925 628 315 389 499 314 216 215 692 600 149 283 826 648 415 639 666 849 273 536 683 339 747 564 380 483 368 555 471 500 959 364 337 441 648 655 342 542 605 676 386 643 80 628 581 149 544 560 9...
result:
ok 1000 lines
Test #8:
score: 0
Accepted
time: 3ms
memory: 23560kb
input:
1000 1000 1 3 2 4 4 6 7 7 10 9 10 12 12 14 14 15 18 19 18 21 21 23 23 23 24 27 27 29 28 29 31 31 33 33 34 36 37 38 38 39 41 41 42 43 44 46 46 49 49 49 50 52 52 55 55 56 58 59 59 59 60 63 64 63 65 65 68 69 69 70 72 71 72 73 76 77 77 79 80 81 82 83 82 83 86 86 88 87 90 89 91 93 93 95 94 97 98 98 98 10...
output:
783 72 634 21 295 234 337 241 823 69 52 39 9 209 270 21 478 802 576 49 232 145 583 516 361 46 519 651 150 459 195 204 31 602 553 266 10 656 398 98 331 584 29 332 296 357 198 595 241 239 401 414 543 288 144 283 187 277 222 803 732 503 2 195 620 481 320 155 438 276 59 142 538 684 127 192 446 243 491 2...
result:
ok 1000 lines
Test #9:
score: 0
Accepted
time: 2178ms
memory: 46808kb
input:
200000 200000 4700652 -5734778 3503665 -6188002 8657410 2276806 -6431469 9627247 9673670 9221683 -3908423 -3069613 -653905 2608836 -4959288 -3108645 2053787 -5840353 259545 9847990 2267414 4231267 8319662 9920009 1973822 3854711 9434531 5938280 -5348422 -4062145 -5060918 -3946777 -7934092 7908462 83...
output:
531534449 60349244 698110493 683183122 239017077 155761236 198479042 224389969 53360136 280044750 690025597 359180266 155492131 100215867 7489229 371149856 257552128 756373561 625758735 10281065 33154057 331682245 187783019 356644222 284214063 184871804 232220709 282778596 659349476 574267601 271559...
result:
ok 200000 lines
Test #10:
score: 0
Accepted
time: 1574ms
memory: 46400kb
input:
200000 200000 1000000000 1000000000 1000000000 994665379 991463472 993592249 990545330 1000000000 1000000000 993709443 993048450 993175969 1000000000 1000000000 1000000000 1000000000 996652523 1000000000 992737565 1000000000 995381198 999029778 994486837 1000000000 1000000000 1000000000 993523414 99...
output:
435875275 457648009 211124733 489445386 272681020 170279466 457584046 180315969 724633614 337953745 382261536 544196655 49729496 125390351 80990952 414848358 237788201 264980067 590869611 767628306 442404587 573389407 358308533 673491043 546282286 623796355 310334534 305536304 643892535 451194211 31...
result:
ok 200000 lines
Test #11:
score: 0
Accepted
time: 1441ms
memory: 45112kb
input:
200000 200000 999936527 1000000000 1000000000 999911064 1000000000 999931025 999987503 999873607 999979442 999867372 999998797 999903420 999942880 999836369 999961944 999997043 999859703 1000000000 999872353 999967979 999895588 999873633 999989612 999939739 999929350 999959172 999826478 999898163 99...
output:
685852606 779027428 767670633 407552348 429157344 536572435 820750082 343199906 153240019 172312558 696380287 469815009 494985027 476719828 619352415 34133816 684452544 206679853 506577503 272757735 230547389 483884971 511887454 396592355 161362798 407519861 605254754 258882877 746577675 73817816 75...
result:
ok 200000 lines
Test #12:
score: 0
Accepted
time: 2666ms
memory: 56932kb
input:
200000 200000 29091 38973 -43929 -59096 85131 -48337 55517 -33006 114388 88422 7767 -40627 51481 72946 50475 -11447 34620 163684 152282 17662 127085 117685 96487 130743 48134 216283 135263 86053 82895 96458 120002 55804 119261 211075 164992 157722 254034 265948 189624 138315 217932 180546 277174 157...
output:
243257560 912832934 310015430 101031560 763481383 163629518 514370005 76106312 84131976 6965181 562147379 643978961 377798707 623798585 726189886 624382491 700519954 442408520 215468449 128115935 259664291 514835375 319905852 89344678 414911644 447441446 407846688 188468274 273723302 73973026 385489...
result:
ok 200000 lines
Test #13:
score: 0
Accepted
time: 1997ms
memory: 46364kb
input:
200000 200000 478661126 262135998 865858988 810996444 591942227 735500821 501689749 50371518 517447906 446463295 608437123 167043833 827378253 748574239 756186328 580692189 517172087 443374960 523720487 881889997 117184442 337424808 411056272 500688800 480471810 143343364 535362952 859590020 5707259...
output:
272999720 315747073 257419408 189314016 356413659 147502771 180971112 483448182 426842843 378086080 176669194 80835598 216151657 369651435 384795439 496220857 86118937 348241535 444535257 387577828 147119493 342572677 34041459 330955795 468414923 484368631 268057725 393103897 58717209 282747703 3721...
result:
ok 200000 lines
Test #14:
score: 0
Accepted
time: 1824ms
memory: 43200kb
input:
200000 200000 294832171 -327658233 662058359 -810653343 -625990848 120657884 -976742718 729067584 -794355628 -907624514 -18150063 881125723 60482279 562743356 -401926055 135101492 -933157390 831548262 344876913 312305225 605857917 170214669 -806582706 -796932016 988860514 -674531379 -806347473 -3319...
output:
stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with parents stay with pa...
result:
ok 200000 lines
Test #15:
score: -100
Time Limit Exceeded
input:
200000 200000 -115 5684 9666 14889 19500 24791 29979 35076 39517 44226 49871 55618 60521 65324 70881 75009 80102 85772 90581 95968 100435 105969 110891 115806 120783 124075 129105 134658 140322 144984 150821 155933 160753 165985 170677 174002 180757 184590 189474 194645 200562 205274 209745 214890 2...
output:
487754816 148845568 533460296 274270708 334714248 516345330 122364942 464210262 586120601 753660346 824860348 298260873 296325973 477055095 361450664 206315763 91844684 138950455 147594323 399949576 533145826 306884304 335329718 313459627 750359129 79690485 537295793 877189280 664030013 266225862 64...