编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#112840 #1461. slecy Accepted 100 5788 ms 98196 K C++ 17 / 3.0 K 7k1danWhen 2024-07-12 15:51:57
显示原始代码
#include <bits/stdc++.h>
using namespace std;

#define ONLINE
#ifndef ONLINE
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) ;
#endif

using LL = long long;
using PII = pair<int, int>;

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()

//快读
template <typename T>
inline T READ() {
    T x = 0;
    bool f = 0;
    char c = getchar();
    while (!isdigit(c)) f |= (c == '-'), c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    return f ? -x : x;
}
inline int read() { return READ<int>(); }
inline LL readLL() { return READ<LL>(); }
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

#define N 500010
namespace ST_C {  // Sparse Table Constant
vector<int> Logn;
void init(int maxn = N) {
    Logn.resize(maxn);
    Logn[1] = 0, Logn[2] = 1;
    for (int i = 3; i < maxn; i++) {
        Logn[i] = Logn[i / 2] + 1;
    }
}
}  // namespace ST_C
template <typename T>
class ST {
    using VT = vector<T>;
    using VVT = vector<VT>;
    using func_t = function<T(const T&, const T&)>;  // RMQ函数,也可以用lambda表达式
    VVT a;                                           // a is Sparse Table
    func_t op;

public:
    ST() {}
    ST(const vector<T>& v, int n, func_t func) {
        init(v, n, func);  // v的有效下标为 1~n
    }
    void init(const vector<T>& v, int n, func_t func) {
        op = func;                     // e.g.
        int mx_l = ST_C::Logn[n] + 1;  // max log
        a.assign(n + 1, VT(mx_l, 0));
        for (int i = 1; i <= n; i++) {
            a[i][0] = v[i];
        }
        for (int j = 1; j < mx_l; j++) {
            int p = (1 << (j - 1));
            for (int i = 1; i + p <= n; i++) {
                a[i][j] = op(a[i][j - 1], a[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    T query(int l, int r) {
        int lt = r - l + 1;
        int p = ST_C::Logn[lt];
        return op(a[l][p], a[r - (1 << p) + 1][p]);
    }
};

template <typename T>  // T is int or LL
class FenTree {
private:
    int n;
    vector<T> c;
    inline int lowbit(const int& x) { return x & (-x); }

public:
    FenTree() {}
    FenTree(int n_) { init(n_); }
    void init(int n_) { c.assign(n = n_, T(0)); }
    void add(int i, int x) {
        for (; i < n; i += lowbit(i)) c[i] += x;
    }
    T query(int i) {
        if (i <= 0)
            return 0;
        T res = 0;
        for (; i; i -= lowbit(i)) res += c[i];
        return res;
    }
};

int main() {
    ST_C::init();  //初始化
    int n = read(), m = read();
    vector<int> a(n + 1), dp;
    FenTree<int> fen;
    for (int i = 1; i <= n; i++) a[i] = read();
    auto max_int = [](const int& x, const int& y) -> int { return x > y ? x : y; };
    auto min_int = [](const int& x, const int& y) -> int { return x < y ? x : y; };
    ST<int> mx(a, n, max_int), mn(a, n, min_int);
    auto check = [&](const int& lim) -> bool {
        debug("lim=%d\n", lim);
        dp.assign(n + 1, 0);
        dp[0] = 1;
        fen.init(n + 1);
        for (int i = 1, opt = 1; i <= n; i++) {
            while (mx.query(opt, i) - mn.query(opt, i) > lim) opt++;
            if (i < m)
                continue;
            debug("\t\ti=%d opt=%d %d\n", i, opt, i - opt + 1);
            if (i - opt + 1 < m)
                continue;
            debug("\t\tquery(%d,%d)\n", opt - 1, i - m);
            if (opt == 1 || fen.query(i - m) - fen.query(opt - 2) > 0) {
                debug("\tdp[%d]=1 opt=%d\n", i, opt);
                dp[i] = 1;
                fen.add(i, 1);
            }
        }
        return dp[n] > 0;
    };
    int l = 0, r = 1e9, mid, ans = 1e9;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:5 ms
内存:2276 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
用时:6 ms
内存:2244 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
用时:6 ms
内存:2304 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
用时:6 ms
内存:2688 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
用时:5 ms
内存:2752 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
用时:10 ms
内存:3136 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
用时:10 ms
内存:3080 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
用时:11 ms
内存:3072 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
用时:12 ms
内存:3008 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
用时:8 ms
内存:3064 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
用时:351 ms
内存:52548 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
用时:398 ms
内存:52480 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
用时:983 ms
内存:98120 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
用时:582 ms
内存:98152 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
用时:864 ms
内存:98176 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
用时:508 ms
内存:98132 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
用时:515 ms
内存:98196 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
用时:458 ms
内存:98080 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
用时:620 ms
内存:98176 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
用时:430 ms
内存:98116 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