This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = pair<ld, int>;
using pii = pair<int, int>;
#define f first
#define s second
const int inf = numeric_limits<int> :: max();
const ll infll = 1e18;
struct ST{
vector<ld> t, p;
vector<int> k;
int n;
void build(int v, int tl, int tr){
if (tl == tr){
k[v] = tl;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
build(vv, tl, tm);
build(vv + 1, tm + 1, tr);
t[v] = tl;
}
ST(int ns){
n = ns;
t.resize(4 * n);
p.resize(4 * n);
k.resize(4 * n);
build(1, 1, n);
}
void push(int& v, int& vv){
if (!p[v]) return;
p[vv] += p[v]; t[vv] += p[v];
p[vv + 1] += p[v]; t[vv + 1] += p[v];
p[v] = 0;
}
void add(int v, int tl, int tr, int& l, int& r, ld& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
t[v] += x;
p[v] += x;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
add(vv, tl, tm, l, r, x);
add(vv + 1, tm + 1, tr, l, r, x);
if (t[vv] > t[vv + 1]){
t[v] = t[vv + 1];
k[v] = k[vv + 1];
}
else {
t[v] = t[vv];
k[v] = k[vv];
}
t[v] = min(t[vv], t[vv + 1]);
}
void add(int l, int r, ld x){
if (l > r) return;
add(1, 1, n, l, r, x);
}
pll get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return {infll, 0};
if (l <= tl && tr <= r){
return {t[v], k[v]};
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
return min(get(vv, tl, tm, l, r), get(vv + 1, tm + 1, tr, l, r));
}
pll get(int l, int r){
if (l > r) return {inf, 0};
return get(1, 1, n, l, r);
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, d, t; cin>>n>>d>>t;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++){
cin>>a[i];
}
vector<int> h(n + 1);
int mx = 0, cnt = 0;
for (int j = 1; j <= n; j++){
if (a[j] <= t){
int m = t - a[j];
mx = max(mx, j + m);
}
cnt += (j <= mx);
h[j] = cnt;
}
vector<int> r(n + 1);
for (int i = 1; i <= n; i++){
if (a[i] > t) continue;
int m = t - a[i];
r[i] = i + m;
}
const int lg = ceil(log2(n));
vector<vector<int>> sp(n + 1, vector<int>(lg));
for (int i = 1; i <= n; i++){
sp[i][0] = r[i];
}
for (int j = 1; j < lg; j++){
for (int i = 1; i + (1 << j) <= n + 1; i++){
sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
}
}
vector<int> log(n + 1);
for (int i = 2; i <= n; i++){
log[i] = log[i / 2] + 1;
}
auto check = [&](int x, int y){
int k = log[y - x + 1];
return max(sp[x][k], sp[y - (1 << k) + 1][k]) >= y;
};
vector<int> f(n);
for (int i = 1; i < n; i++){
auto good = [&](int m){
return check(m, i + 1);
};
int l = 0, r = i + 1;
while (l + 1 < r){
int m = (l + r) / 2;
if (good(m)){
l = m;
}
else {
r = m - 1;
}
}
if (good(r)) l = r;
f[i] = l;
}
auto solve = [&](ld m){
pll dp[n + 1];
ST T(n);
for (int i = 1; i <= n; i++){
dp[i] = {h[i], 0};
T.add(1, f[i - 1] - 1, 1);
auto [v, j] = T.get(1, i - 1);
dp[i] = min(dp[i], {v + m, dp[j].s + 1});
T.add(i, i, dp[i].f);
}
return dp[n];
};
ld lb = 0, rb = n;
int tt = 30;
while (tt-- && (rb - lb) > 1e-4){
ld m = (lb + rb) / 2;
auto [v, k] = solve(m);
if (k > d){
lb = m;
}
else {
rb = m;
}
}
auto [v, k] = solve(lb);
cout<<round(v - lb * d)<<"\n";
}
Compilation message (stderr)
prison.cpp:1:1: error: 'include' does not name a type
1 | include <bits/stdc++.h>
| ^~~~~~~
prison.cpp:5:13: error: 'pair' does not name a type
5 | using pll = pair<ld, int>;
| ^~~~
prison.cpp:6:13: error: 'pair' does not name a type
6 | using pii = pair<int, int>;
| ^~~~
prison.cpp:9:17: error: 'numeric_limits' was not declared in this scope
9 | const int inf = numeric_limits<int> :: max();
| ^~~~~~~~~~~~~~
prison.cpp:9:32: error: expected primary-expression before 'int'
9 | const int inf = numeric_limits<int> :: max();
| ^~~
prison.cpp:13:5: error: 'vector' does not name a type
13 | vector<ld> t, p;
| ^~~~~~
prison.cpp:14:5: error: 'vector' does not name a type
14 | vector<int> k;
| ^~~~~~
prison.cpp:66:5: error: 'pll' does not name a type; did you mean 'll'?
66 | pll get(int v, int tl, int tr, int& l, int& r){
| ^~~
| ll
prison.cpp:75:5: error: 'pll' does not name a type; did you mean 'll'?
75 | pll get(int l, int r){
| ^~~
| ll
prison.cpp: In member function 'void ST::build(int, int, int)':
prison.cpp:19:13: error: 'k' was not declared in this scope
19 | k[v] = tl;
| ^
prison.cpp:25:9: error: 't' was not declared in this scope; did you mean 'tm'?
25 | t[v] = tl;
| ^
| tm
prison.cpp: In constructor 'ST::ST(int)':
prison.cpp:30:9: error: 't' was not declared in this scope
30 | t.resize(4 * n);
| ^
prison.cpp:31:9: error: 'p' was not declared in this scope
31 | p.resize(4 * n);
| ^
prison.cpp:32:9: error: 'k' was not declared in this scope
32 | k.resize(4 * n);
| ^
prison.cpp: In member function 'void ST::push(int&, int&)':
prison.cpp:36:14: error: 'p' was not declared in this scope
36 | if (!p[v]) return;
| ^
prison.cpp:37:9: error: 'p' was not declared in this scope
37 | p[vv] += p[v]; t[vv] += p[v];
| ^
prison.cpp:37:24: error: 't' was not declared in this scope
37 | p[vv] += p[v]; t[vv] += p[v];
| ^
prison.cpp: In member function 'void ST::add(int, int, int, int&, int&, ld&)':
prison.cpp:44:13: error: 't' was not declared in this scope
44 | t[v] += x;
| ^
prison.cpp:45:13: error: 'p' was not declared in this scope
45 | p[v] += x;
| ^
prison.cpp:52:13: error: 't' was not declared in this scope; did you mean 'tm'?
52 | if (t[vv] > t[vv + 1]){
| ^
| tm
prison.cpp:54:13: error: 'k' was not declared in this scope
54 | k[v] = k[vv + 1];
| ^
prison.cpp:58:13: error: 'k' was not declared in this scope
58 | k[v] = k[vv];
| ^
prison.cpp:60:9: error: 't' was not declared in this scope; did you mean 'tm'?
60 | t[v] = min(t[vv], t[vv + 1]);
| ^
| tm
prison.cpp:60:16: error: 'min' was not declared in this scope
60 | t[v] = min(t[vv], t[vv + 1]);
| ^~~
prison.cpp: In function 'int main()':
prison.cpp:82:5: error: 'ios_base' has not been declared
82 | ios_base::sync_with_stdio(0);
| ^~~~~~~~
prison.cpp:83:5: error: 'cin' was not declared in this scope
83 | cin.tie(0);
| ^~~
prison.cpp:84:5: error: 'cout' was not declared in this scope
84 | cout.tie(0);
| ^~~~
prison.cpp:87:5: error: 'vector' was not declared in this scope
87 | vector<int> a(n + 1);
| ^~~~~~
prison.cpp:87:12: error: expected primary-expression before 'int'
87 | vector<int> a(n + 1);
| ^~~
prison.cpp:89:14: error: 'a' was not declared in this scope
89 | cin>>a[i];
| ^
prison.cpp:92:12: error: expected primary-expression before 'int'
92 | vector<int> h(n + 1);
| ^~~
prison.cpp:95:13: error: 'a' was not declared in this scope
95 | if (a[j] <= t){
| ^
prison.cpp:97:18: error: 'max' was not declared in this scope; did you mean 'mx'?
97 | mx = max(mx, j + m);
| ^~~
| mx
prison.cpp:100:9: error: 'h' was not declared in this scope
100 | h[j] = cnt;
| ^
prison.cpp:103:12: error: expected primary-expression before 'int'
103 | vector<int> r(n + 1);
| ^~~
prison.cpp:105:13: error: 'a' was not declared in this scope
105 | if (a[i] > t) continue;
| ^
prison.cpp:106:21: error: 'a' was not declared in this scope
106 | int m = t - a[i];
| ^
prison.cpp:107:9: error: 'r' was not declared in this scope
107 | r[i] = i + m;
| ^
prison.cpp:110:25: error: 'log2' was not declared in this scope; did you mean 'lg'?
110 | const int lg = ceil(log2(n));
| ^~~~
| lg
prison.cpp:110:20: error: 'ceil' was not declared in this scope
110 | const int lg = ceil(log2(n));
| ^~~~
prison.cpp:111:19: error: expected primary-expression before 'int'
111 | vector<vector<int>> sp(n + 1, vector<int>(lg));
| ^~~
prison.cpp:113:9: error: 'sp' was not declared in this scope; did you mean 's'?
113 | sp[i][0] = r[i];
| ^~
| s
prison.cpp:113:20: error: 'r' was not declared in this scope
113 | sp[i][0] = r[i];
| ^
prison.cpp:117:13: error: 'sp' was not declared in this scope; did you mean 's'?
117 | sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
| ^~
| s
prison.cpp:117:24: error: 'max' was not declared in this scope; did you mean 'mx'?
117 | sp[i][j] = max(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
| ^~~
| mx
prison.cpp:120:12: error: expected primary-expression before 'int'
120 | vector<int> log(n + 1);
| ^~~
prison.cpp:122:9: error: 'log' was not declared in this scope; did you mean 'lg'?
122 | log[i] = log[i / 2] + 1;
| ^~~
| lg
prison.cpp: In lambda function:
prison.cpp:126:17: error: 'log' was not declared in this scope; did you mean 'lg'?
126 | int k = log[y - x + 1];
| ^~~
| lg
prison.cpp:127:20: error: 'sp' was not declared in this scope; did you mean 's'?
127 | return max(sp[x][k], sp[y - (1 << k) + 1][k]) >= y;
| ^~
| s
prison.cpp:127:16: error: 'max' was not declared in this scope; did you mean 'mx'?
127 | return max(sp[x][k], sp[y - (1 << k) + 1][k]) >= y;
| ^~~
| mx
prison.cpp: In function 'int main()':
prison.cpp:130:12: error: expected primary-expression before 'int'
130 | vector<int> f(n);
| ^~~
prison.cpp:7:11: error: 'first' was not declared in this scope
7 | #define f first
| ^~~~~
prison.cpp:146:9: note: in expansion of macro 'f'
146 | f[i] = l;
| ^
prison.cpp: In lambda function:
prison.cpp:150:9: error: 'pll' was not declared in this scope; did you mean 'll'?
150 | pll dp[n + 1];
| ^~~
| ll
prison.cpp:153:13: error: 'dp' was not declared in this scope; did you mean 'd'?
153 | dp[i] = {h[i], 0};
| ^~
| d
prison.cpp:153:22: error: 'h' was not declared in this scope
153 | dp[i] = {h[i], 0};
| ^
prison.cpp:7:11: error: 'first' was not declared in this scope
7 | #define f first
| ^~~~~
prison.cpp:154:22: note: in expansion of macro 'f'
154 | T.add(1, f[i - 1] - 1, 1);
| ^
prison.cpp:155:29: error: 'struct ST' has no member named 'get'
155 | auto [v, j] = T.get(1, i - 1);
| ^~~
prison.cpp:156:21: error: 'min' was not declared in this scope; did you mean 'main'?
156 | dp[i] = min(dp[i], {v + m, dp[j].s + 1});
| ^~~
| main
prison.cpp:159:16: error: 'dp' was not declared in this scope; did you mean 'd'?
159 | return dp[n];
| ^~
| d
prison.cpp: In function 'int main()':
prison.cpp:176:11: error: 'round' was not declared in this scope
176 | cout<<round(v - lb * d)<<"\n";
| ^~~~~