이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;
int n, d, t;
const int N = 2e6 + 5;
int arr[N];
int all = 0;
vector<int> adj[N];
int depth[N];
vector<int> have;
void init() {
}
void input() {
cin >> n >> d >> t;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
}
void creadj() {
vector<int> have;
bool can[n + 1];
int ends[n + 1];
fill(ends + 1, ends + n + 1, 0);
all = 1;
for (int i = 1; i <= n; i++) {
while (!have.empty()) {
int ind = have.back();
if (arr[ind] - ind < arr[i] - i) {
break;
}
have.pop_back();
}
have.pb(i);
if (arr[have[0]] - have[0] <= t - i) {
int l = 0, r = sz(have);
while (l + 1 != r) {
int m = (l + r) / 2;
if (arr[have[m]] - have[m] <= t - i) {
l = m;
}
else {
r = m;
}
}
all++;
if (have[l] != i) {
ends[have[l]]++;
can[i] = true;
}
else {
can[i] = false;
}
}
else {
can[i] = false;
}
}
stack<int> verts;
verts.push(0);
for (int i = n; i >= 1; i--) {
if (!can[i]) {
continue;
}
adj[verts.top()].pb(i);
verts.push(i);
for (int j = 0; j < ends[i]; j++) {
verts.pop();
}
}
}
void dfsdepth(int u) {
for (auto v : adj[u]) {
dfsdepth(v);
depth[u] = max(depth[u], depth[v] + 1);
}
for (int i = 0; i < sz(adj[u]); i++) {
if (depth[adj[u][0]] < depth[adj[u][i]]) {
swap(adj[u][0], adj[u][i]);
}
}
}
void dfs(int u, int d) {
if (adj[u].empty()) {
have.pb(d);
return;
}
dfs(adj[u][0], d + 1);
for (auto v : adj[u]) {
if (v != adj[u][0]) {
dfs(v, 1);
}
}
}
void solve() {
creadj();
dfsdepth(0);
dfs(0, 1);
sort(have.begin(), have.end());
reverse(have.begin(), have.end());
for (int i = 0; i < d && i < sz(have); i++) {
all -= have[i];
}
cout << all;
}
void output() {
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int number_of_testcases = 1;
//cin >> number_of_testcases;
while (number_of_testcases--) {
init();
input();
solve();
output();
}
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... |