编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#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;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:7 ms
内存:2296 KiB

输入文件(1.in

10 3
2 5 10 9 4 2 10 6 6 4

答案文件(1.out

8

用户输出

8

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:5 ms
内存:2296 KiB

输入文件(2.in

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>

答案文件(2.out

941

用户输出

941

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:7 ms
内存:2268 KiB

输入文件(3.in

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>

答案文件(3.out

994

用户输出

994

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:12 ms
内存:2312 KiB

输入文件(4.in

2998 103
719789 385667 503327 690848 5817 824736 566534 909189 239674 187750 997354 12429 364402 505
<20572 bytes omitted>

答案文件(4.out

998108

用户输出

998108

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:11 ms
内存:2304 KiB

输入文件(5.in

3005 994
466609 497107 980267 181023 295275 129102 706586 149195 748088 202635 978263 807351 496045 
<20623 bytes omitted>

答案文件(5.out

999538

用户输出

999538

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:14 ms
内存:2240 KiB

输入文件(6.in

4999 10
137081837 284078481 190559864 763687683 971858818 46985237 553785132 529023601 907309023 102
<49197 bytes omitted>

答案文件(6.out

982313064

用户输出

982313064

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:14 ms
内存:2296 KiB

输入文件(7.in

4996 71
817572379 841265153 985092212 258879986 969354686 274497647 55515178 607378505 773597758 720
<49250 bytes omitted>

答案文件(7.out

996437191

用户输出

996437191

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:14 ms
内存:2244 KiB

输入文件(8.in

5001 101
459925685 555296170 247245605 709935831 735045381 372363852 831305189 894346704 482697636 3
<49248 bytes omitted>

答案文件(8.out

998660006

用户输出

998660006

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:15 ms
内存:2304 KiB

输入文件(9.in

5001 999
299728127 132697032 625319568 93665377 221796659 9727812 534527799 134659002 893961557 4181
<49269 bytes omitted>

答案文件(9.out

999919205

用户输出

999919205

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:14 ms
内存:2252 KiB

输入文件(10.in

5005 5000
525818001 960876299 440781143 714148333 335584670 926721811 396656304 549095111 807528349 
<49312 bytes omitted>

答案文件(10.out

999999999

用户输出

999999999

系统信息

Exited with return code 0
测试点 #11
Accepted
得分:100
用时:487 ms
内存:4348 KiB

输入文件(11.in

262143 512
828462989 791421488 580566535 153185879 972901423 116145686 202806706 259598377 694784045
<2587564 bytes omitted>

答案文件(11.out

999899849

用户输出

999899849

系统信息

Exited with return code 0
测试点 #12
Accepted
得分:100
用时:468 ms
内存:4344 KiB

输入文件(12.in

262144 512
46874324 784679853 945570405 497270803 325016673 356820897 333233108 58266749 25120443 21
<2587170 bytes omitted>

答案文件(12.out

999759568

用户输出

999759568

系统信息

Exited with return code 0
测试点 #13
Accepted
得分:100
用时:881 ms
内存:6080 KiB

输入文件(13.in

499999 10
950705934 252683312 140493294 154892170 545467313 559015228 153098005 47505168 574885069 2
<4935423 bytes omitted>

答案文件(13.out

997561897

用户输出

997561897

系统信息

Exited with return code 0
测试点 #14
Accepted
得分:100
用时:558 ms
内存:10276 KiB

输入文件(14.in

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>

答案文件(14.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #15
Accepted
得分:100
用时:892 ms
内存:6196 KiB

输入文件(15.in

499998 724
457030458 981451846 436090259 704145396 473261476 212933785 366799540 588076249 729043455
<4935072 bytes omitted>

答案文件(15.out

999766318

用户输出

999766318

系统信息

Exited with return code 0
测试点 #16
Accepted
得分:100
用时:569 ms
内存:10364 KiB

输入文件(16.in

499996 853
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1
<5499867 bytes omitted>

答案文件(16.out

0

用户输出

0

系统信息

Exited with return code 0
测试点 #17
Accepted
得分:100
用时:864 ms
内存:6196 KiB

输入文件(17.in

500000 500000
155092102 985014079 14863541 335064091 468784932 853006455 63364617 14916353 589368055
<4935570 bytes omitted>

答案文件(17.out

999999999

用户输出

999999999

系统信息

Exited with return code 0
测试点 #18
Accepted
得分:100
用时:782 ms
内存:6196 KiB

输入文件(18.in

500000 250003
640164463 799370806 580304545 84268480 34077050 304286015 891523127 345217253 21630964
<4934898 bytes omitted>

答案文件(18.out

937719765

用户输出

937719765

系统信息

Exited with return code 0
测试点 #19
Accepted
得分:100
用时:579 ms
内存:8228 KiB

输入文件(19.in

500000 250002
10088 10914 11030 11676 16096 20309 21825 24475 25237 27141 28988 37610 43256 43972 46
<4935483 bytes omitted>

答案文件(19.out

998234265

用户输出

998234265

系统信息

Exited with return code 0
测试点 #20
Accepted
得分:100
用时:577 ms
内存:8252 KiB

输入文件(20.in

500000 250001
975 1216 1344 1445 3799 4622 4739 6490 9807 10698 10877 11917 12874 13458 14965 15098 
<4934975 bytes omitted>

答案文件(20.out

922338146

用户输出

922338146

系统信息

Exited with return code 0