QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#537710 | #5258. Mortgage | UESTC_DECAYALI | WA | 2ms | 7916kb | C++20 | 2.0kb | 2024-08-30 17:38:37 | 2024-08-30 17:38:38 |
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) L=M1;
else R = M2;
// 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: 2ms
memory: 7676kb
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: 2ms
memory: 7916kb
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: 1ms
memory: 3784kb
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: 1ms
memory: 3696kb
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: -100
Wrong Answer
time: 0ms
memory: 3784kb
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 185 490 557 177 84 211 688 315 784 228 313 stay with parents 53 408 218 764 451 127 371 823 805 349 552 260 523 186 500 3 52 411 199 699 422 435 324 244 134 304 585 108 583 200 55 236 310 260 879 712 193 336 311 108 stay with parents 51 434 stay with parents 186 265 495 319 544 1...
result:
wrong answer 6th lines differ - expected: '1', found: '185'