QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#537718 | #5258. Mortgage | UESTC_DECAYALI | WA | 171ms | 27456kb | C++20 | 2.0kb | 2024-08-30 17:43:48 | 2024-08-30 17:43:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n, m, A[N], sum[N];
struct Node{
int R, id;
bool operator<(const Node &b)const{return R!=b.R ? R>b.R : id<b.id;}
};
vector<Node> qry[N];
int ans[N];
struct Convh{
vector<int> stk; int sz=0;
void add(int id){
while (sz>1 &&
(sum[stk[sz-1]]-sum[id])*(stk[sz-2]-stk[sz-1]) >
(sum[stk[sz-2]]-sum[stk[sz-1]])*(stk[sz-1]-id))
stk.pop_back(), --sz;
stk.push_back(id); ++sz;
}
int find(int id){
int L=0, R=sz-1;
while (R - L > 20){
int M1 = L+(R-L)/2, M2 = M1+1;
int res1 = (sum[stk[M1]]-sum[id])*(stk[M2]-id);
int res2 = (sum[stk[M2]]-sum[id])*(stk[M1]-id);
if (res1 == res2) L=R;
else if (res1 < res2) R = M2;
else L = M1;
// std::cerr << "FUCK\n";
}
int ans = 0x7f7f7f7f;
while(L <= R) ans = min(ans, (sum[stk[L]]-sum[id])/(stk[L]-id)), L++;
if (ans>=0) return ans;
else return -1;
}
};
Convh c[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i=1; i<=n; ++i) cin >> A[i], sum[i] = sum[i-1]+A[i];
for (int i=1; i<=m; ++i){
int s, k; cin >> s >> k;
qry[s-1].push_back(Node{s+k-1, i});
}
for (int i=0; i<n; ++i) sort(qry[i].begin(), qry[i].end());
for (int i=n; i>=0; --i){
for(auto [q, id]: qry[i]) {
int l = i + 1, r = q + 1, a = 0x7f7f7f7f;
for(int j = r; j; j -= j&-j) if(c[j].sz) a = std::min(a, c[j].find(l - 1));// std::cerr << "FUCK\n";
ans[id] = a;
}
for(int j = i + 1; j <= n + 1; j += j&-j) c[j].add(i);// std::cerr << "Blyat\n";
}
for(int i = 1; i <= m; ++i) {
if(ans[i] < 0) std::cout << "stay with parents\n";
else std::cout << ans[i] << char(10);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7664kb
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: 1ms
memory: 3820kb
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: 2ms
memory: 7844kb
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: 0ms
memory: 5784kb
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: 0ms
memory: 3844kb
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: 1ms
memory: 5796kb
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: 2ms
memory: 7892kb
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: 0ms
memory: 3764kb
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: -100
Wrong Answer
time: 171ms
memory: 27456kb
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:
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:
wrong answer 1st lines differ - expected: '531534449', found: 'stay with parents'