用户输出
8
系统信息
Exited with return code 0
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#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;
}
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