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;
#define ll long long
#define pii pair<int, int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvb vector<vb>
#define vvi vector<vi>
#define vvpii vector<vpii>
#define sz(x) (int)(x).size()
int N, D, T;
vi P;
struct segtree
{
int size;
vi arr;
void init(int n)
{
size = 1;
while (size < n)
size *= 2;
arr.assign(2 * size, 0);
}
int query(int l, int r) { return query(l, r, 1, 0, size); }
int query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return 0;
int m = (lx + rx) / 2;
return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx);
}
void block(int l, int r) { block(l, r, 1, 0, size); }
void block(int l, int r, int x, int lx, int rx)
{
if (rx - lx == 1)
arr[x] = 1;
if (r <= lx || rx <= l || arr[x] == rx - lx)
return;
int m = (lx + rx) / 2;
block(l, r, 2 * x, lx, m);
block(l, r, 2 * x + 1, m, rx);
arr[x] = arr[2 * x] + arr[2 * x + 1];
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> D >> T;
D = min(D, N);
P.resize(N);
for (int i = 0; i < N; ++i)
cin >> P[i];
vi pref(N + 1, 0); // number of protestants in range [0, i)
int border = -1;
for (int i = 0; i < N; ++i)
{
border = max(border, i + T - P[i]);
pref[i + 1] = pref[i];
if (i <= border)
pref[i + 1] += 1;
}
vi suff(N + 1, 0); // number of protestants in range [i, N-1]
segtree seg;
seg.init(N);
for (int i = N - 1; i >= 0; --i)
{
if (P[i] <= T)
seg.block(i, i + T - P[i] + 1);
suff[i] = seg.query(0, N);
}
int ans = suff[0];
for (int i = 0; i < N; ++i)
{
ans = min(ans, suff[i] + pref[i]);
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |