#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
const int N = 2e6 + 20, inf = 1e8;
int a[N];
stack<int> st;
vector<pair<int, int>> vt;
pair<int, int> seg[N << 2]; // <mx, ind>
int ans[N];
int n, D, T;
bool compa(pair<int, int> p1, pair<int, int> p2) {return p1.S - p1.F < p2.S - p2.F;}
void build(int u = 1, int s = 0, int e = N)
{
if (e - s < 2)
{
seg[u] = {0, s};
return;
}
int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
build(lc, s, mid); build(rc, mid, e);
seg[u] = max(seg[lc], seg[rc]);
return;
}
void add(int ind, int x, int u = 1, int s = 0, int e = N)
{
if (e - s < 2)
{
seg[u].F += x;
return;
}
int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
if (ind < mid)
add(ind, x, lc, s, mid);
else
add(ind, x, rc, mid, e);
seg[u] = max(seg[lc], seg[rc]);
return;
}
pair<int, int> get(int l, int r, int u = 1, int s = 0, int e = N)
{
if (e <= l || r <= s) return {-inf, -inf};
if (l <= s && r >= e) return seg[u];
int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}
void build2(int u = 1, int s = 0, int e = N)
{
if (e - s < 2)
{
if (s < n - 1)
{
ans[s] = -seg[u].F;
// cout << " " << s + 1 << " " << seg[u].F << '\n';
}
return;
}
int lc = u << 1, rc = lc | 1, mid = (s + e) >> 1;
build2(lc, s, mid); build2(rc, mid, e);
return;
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> D >> T;
for (int i = 0; i < n; i++)
{
cin >> a[i];
st.push(i);
while (!st.empty())
{
if (a[st.top()] - st.top() > T - i)
{
st.pop();
continue;
}
break;
}
if (st.empty()) continue;
if (st.top() == i) continue;
// cout << " " << i + 1 << " " << st.top() << '\n';
vt.push_back({st.top(), i - 1});
}
sort(vt.begin(), vt.end(), compa);
for (pair<int, int> p : vt)
{
int l = p.F, r = p.S;
int x = get(l, r + 1).S;
// cout << " " << x + 1 << '\n';
add(x, 1);
}
build2();
sort(ans, ans + n - 1);
int bad = 0;
for (int i = 0; i < min(D, n - 1); i++) bad -= ans[i];
cout << n - bad;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
