이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 1e9 + 50;
const int N = 2e6 + 50;
int n, d, t[N], T, par[N];
int seg[N<<2], out[N<<2], lazy[N<<2];
bool vis[N];
int I[N];
void build(int c, int u=1, int tl=1, int tr=n) {
if (tl == tr) {
if (!c) seg[u] = inf;
else seg[u] = 0, out[u] = tl;
return;
}
int md = (tl+tr)/2;
int lc = u<<1;
int rc = u<<1|1;
build(c, lc, tl, md), build(c, rc, md+1, tr);
if (!c) seg[u] = min(seg[lc], seg[rc]);
else seg[u] = max(seg[lc], seg[rc]), out[u] = (seg[lc] > seg[rc]? out[lc]: out[rc]);
}
void shift(int u) {
int lc = u<<1;
int rc = u<<1|1;
seg[lc] += lazy[u];
lazy[lc] += lazy[u];
seg[rc] += lazy[u];
lazy[rc] += lazy[u];
lazy[u] = 0;
}
void upd(int c, int l, int r, int x, int u=1, int tl=1, int tr=n) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
if (!c) seg[u] = min(seg[u], x);
else seg[u] += x, lazy[u] += x;
return;
}
if (c) shift(u);
int md = (tl+tr)/2;
int lc = u<<1;
int rc = u<<1|1;
upd(c, l, r, x, lc, tl, md), upd(c, l, r, x, rc, md+1, tr);
if (!c) seg[u] = min(seg[lc], seg[rc]);
else seg[u] = max(seg[lc], seg[rc]), out[u] = (seg[lc] > seg[rc]? out[lc]: out[rc]);
}
int get(int x, int u=1, int tl=1, int tr=n) {
if (seg[u] > x) return 0;
if (tl == tr) return tl;
int md = (tl+tr)/2;
int lc = u<<1;
int rc = u<<1|1;
int out = get(x, rc, md+1, tr);
if (!out) out = get(x, lc, tl, md);
return out;
}
void solve() {
cin >> n >> d >> T;
for (int i = 1; i <= n; i++) {
cin >> t[i];
}
build(0);
int ans = 0;
for (int i = 1; i <= n; i++) {
upd(0, i, i, t[i]-i);
int x = get(T-i)+1;
if (x > i) continue;
if (x <= 1) {
ans++;
continue;
}
I[i] = x;
}
build(0);
for (int u = n; u >= 1; u--) {
if (!I[u]) continue;
int p = get(I[u]);
upd(0, n-u+1, n-u+1, I[u]);
p = n-p+1;
par[u] = p;
}
build(1);
for (int u = n; u >= 1; u--) {
if (!I[u]) continue;
upd(1, I[u], u, 1);
}
for (int u = 1; u <= n; u++) vis[u] = 0;
vis[n+1] = 1;
for (int t = 1; t <= d; t++) {
int u = out[1];
ans += seg[1];
while (!vis[u]) {
upd(1, I[u], u, -1);
vis[u] = 1;
u = par[u];
}
}
cout << n-ans << endl;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
solve();
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... |