用户输出
8
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#113365 | #1461. slecy | Accepted | 100 | 6770 ms | 10364 K | C++ 11 / 1.4 K | ShwStone | 2024-07-13 12:19:34 |
#include <bits/stdc++.h>
using namespace std;
const int MAXN(5e5 + 5);
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
int n, m;
int a[MAXN], dis[MAXN], sum[MAXN];
bool check(int x) {
deque<int> s1, s2;
int j = 1;
for (int i = 1; i <= n; i++) {
if (!s1.empty() && s1.front() == i - 1)
s1.pop_front();
if (!s2.empty() && s2.front() == i - 1)
s2.pop_front();
while (j <= n && (s1.empty() || max(a[s1.front()], a[j]) - min(a[s2.front()], a[j]) <= x)) {
while (!s1.empty() && a[j] > a[s1.back()]) s1.pop_back();
while (!s2.empty() && a[j] < a[s2.back()]) s2.pop_back();
s1.emplace_back(j), s2.emplace_back(j);
j++;
}
dis[i] = j - 1;
}
memset(sum, 0, sizeof sum);
sum[n + 1] = 1;
for (int i = n; i >= 1; i--) {
sum[i] = sum[i + 1];
if (i + m - 1 > dis[i])
continue;
if (sum[i + m] - sum[dis[i] + 2] > 0)
sum[i]++;
}
return sum[1] > sum[2];
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", a + i);
}
int l = 0, r = 1e9, mid;
while (l < r) {
mid = (l + r) >> 1;
if (check(mid))
r = mid;
else
l = mid + 1;
}
printf("%d\n", l);
return 0;
}
100 11
727 208 498 460 744 963 696 729 924 22 182 104 167 949 439 271 28 85 991 684 648 860 280 831
<294 bytes omitted>
用户输出
941
系统信息
Exited with return code 0
99 23
777 278 377 737 329 633 323 411 975 586 309 150 842 277 906 76 647 12 145 808 412 387 877 786
<291 bytes omitted>
用户输出
994
系统信息
Exited with return code 0
2998 103
719789 385667 503327 690848 5817 824736 566534 909189 239674 187750 997354 12429 364402 505
<20572 bytes omitted>
用户输出
998108
系统信息
Exited with return code 0
3005 994
466609 497107 980267 181023 295275 129102 706586 149195 748088 202635 978263 807351 496045
<20623 bytes omitted>
用户输出
999538
系统信息
Exited with return code 0
4999 10
137081837 284078481 190559864 763687683 971858818 46985237 553785132 529023601 907309023 102
<49197 bytes omitted>
用户输出
982313064
系统信息
Exited with return code 0
4996 71
817572379 841265153 985092212 258879986 969354686 274497647 55515178 607378505 773597758 720
<49250 bytes omitted>
用户输出
996437191
系统信息
Exited with return code 0
5001 101
459925685 555296170 247245605 709935831 735045381 372363852 831305189 894346704 482697636 3
<49248 bytes omitted>
用户输出
998660006
系统信息
Exited with return code 0
5001 999
299728127 132697032 625319568 93665377 221796659 9727812 534527799 134659002 893961557 4181
<49269 bytes omitted>
用户输出
999919205
系统信息
Exited with return code 0
5005 5000
525818001 960876299 440781143 714148333 335584670 926721811 396656304 549095111 807528349
<49312 bytes omitted>
用户输出
999999999
系统信息
Exited with return code 0
262143 512
828462989 791421488 580566535 153185879 972901423 116145686 202806706 259598377 694784045
<2587564 bytes omitted>
用户输出
999899849
系统信息
Exited with return code 0
262144 512
46874324 784679853 945570405 497270803 325016673 356820897 333233108 58266749 25120443 21
<2587170 bytes omitted>
用户输出
999759568
系统信息
Exited with return code 0
499999 10
950705934 252683312 140493294 154892170 545467313 559015228 153098005 47505168 574885069 2
<4935423 bytes omitted>
用户输出
997561897
系统信息
Exited with return code 0
499995 539
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
<999901 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
499998 724
457030458 981451846 436090259 704145396 473261476 212933785 366799540 588076249 729043455
<4935072 bytes omitted>
用户输出
999766318
系统信息
Exited with return code 0
499996 853
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1
<5499867 bytes omitted>
用户输出
0
系统信息
Exited with return code 0
500000 500000
155092102 985014079 14863541 335064091 468784932 853006455 63364617 14916353 589368055
<4935570 bytes omitted>
用户输出
999999999
系统信息
Exited with return code 0
500000 250003
640164463 799370806 580304545 84268480 34077050 304286015 891523127 345217253 21630964
<4934898 bytes omitted>
用户输出
937719765
系统信息
Exited with return code 0
500000 250002
10088 10914 11030 11676 16096 20309 21825 24475 25237 27141 28988 37610 43256 43972 46
<4935483 bytes omitted>
用户输出
998234265
系统信息
Exited with return code 0