이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
bool is = false;
for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
return o << '}';
}
#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif
using ll = long long;
#define int ll
int a[100005];
struct node {
ll mn, mx;
};
node tree[4 * 100005];
int ans = 2e9;
void comb(int x) {
tree[x].mn = min(tree[2 * x].mn, tree[2 * x + 1].mn);
tree[x].mx = max(tree[2 * x].mx, tree[2 * x + 1].mx);
}
void sett(int x, int l, int r, int p, ll v) {
if (l == r) {
tree[x].mn = tree[x].mx = v;
return;
}
int mid = (l + r) / 2;
if (p <= mid) sett(2 * x, l, mid, p, v);
else sett(2 * x + 1, mid + 1, r, p, v);
comb(x);
}
int n, k, t;
int x[100005];
int bigger(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
if (tree[x].mx >= v) {
if (l == r) return l;
int mid = (l + r) / 2;
if (tree[2 * x].mx >= v) return bigger(2 * x, l, mid, ql, qr, v);
else return bigger(2 * x + 1, mid + 1, r, ql, qr, v);
} else {
return -1;
}
}
if (ql > r || l > qr) return -1;
int mid = (l + r) / 2;
int res = bigger(2 * x, l, mid, ql, qr, v);
if (res == -1) res = bigger(2 * x + 1, mid + 1, r, ql, qr, v);
return res;
}
int smaller(int x, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
if (tree[x].mn <= v) {
if (l == r) return l;
int mid = (l + r) / 2;
if (tree[2 * x + 1].mn <= v) return smaller(2 * x + 1, mid + 1, r, ql, qr, v);
else return smaller(2 * x, l, mid, ql, qr, v);
} else {
return -1;
}
}
if (ql > r || l > qr) return -1;
int mid = (l + r) / 2;
int res = smaller(2 * x + 1, mid + 1, r, ql, qr, v);
if (res == -1) return smaller(2 * x, l, mid, ql, qr, v);
return res;
}
bool check(int s) {
int dist = s * t * 2; // in one sec
for (int i = 1; i <= n; i++) {
x[i] = a[i] - dist * i;
sett(1, 1, n + 1, i, x[i]);
}
int tochange = bigger(1, 1, n + 1, k, n + 1, x[k] + 1) - 1;
for (int i = k - 1; i >= 1; i--) {
if (x[i + 1] <= x[i]) {
// dont need help
tochange = bigger(1, 1, n + 1, tochange, n + 1, x[i] + 1) - 1;
} else {
tochange = smaller(1, 1, n + 1, k, tochange, x[i]);
if (tochange == -1) return false;
}
}
return (tochange == n);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("", "r", stdin);
// freopen("", "w", stdout);
cin >> n >> k >> t;
for (int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = a[n];
sett(1, 1, n + 1, n + 1, 1e18);
int lo = 0, hi = 1e10;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(mid)) {
ans = min(ans, mid);
hi = mid - 1;
} else lo = mid + 1;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |