#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e6;
const long long INF = 1e9;
bool vis[MAX_N + 1];
int parent[MAX_N + 1], firstLower[MAX_N + 1], depth[MAX_N + 1], pos[MAX_N + 1];
long long t[MAX_N + 1];
vector<int> adj[MAX_N + 1], opt[MAX_N + 1];
int comp;
void dfs( int u ) {
vis[u] = true;
for ( int v: adj[u] ) {
depth[v] = depth[u] + 1;
dfs( v );
}
if ( adj[u].size() == 0 )
opt[comp].push_back( depth[u] );
}
int main() {
//ifstream cin( ".in" );
cin.tie( NULL );
cout.tie( NULL );
ios_base::sync_with_stdio( false );
int n, d, s;
cin >> n >> d >> s;
for ( int i = 1; i <= n; i++ )
cin >> t[i];
t[0] = -INF;
vector<int> stack;
stack.push_back( 0 );
firstLower[0] = 0;
for ( int i = 1; i <= n; i++ ) {
while ( t[i] - i <= t[stack.back()] - stack.back() )
stack.pop_back();
stack.push_back( i );
int l = 0, r = stack.size();
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( t[stack[mid]] + i - stack[mid] <= s )
l = mid;
else
r = mid;
}
firstLower[i] = stack[l];
}
stack.clear();
stack.push_back( n + 1 );
firstLower[n + 1] = -1;
for ( int i = n; i >= 1; i-- ) {
if ( t[i] <= s )
continue;
int l = 0, r = stack.size();
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( firstLower[stack[mid]] < i )
l = mid;
else
r = mid;
}
parent[i] = stack[l];
adj[parent[i]].push_back( i );
while ( firstLower[i] <= firstLower[stack.back()] )
stack.pop_back();
stack.push_back( i );
}
priority_queue<pair<int, int>> pq;
for ( int i = n; i >= 1; i-- ) {
if ( t[i] <= s )
continue;
depth[i] = 1;
dfs( i );
sort( opt[comp].begin(), opt[comp].end() );
reverse( opt[comp].begin(), opt[comp].end() );
pq.push( { opt[comp][0], comp } );
comp++;
}
int ans = n;
while ( d > 0 && !pq.empty() ) {
auto x = pq.top();
pq.pop();
int c = x.second;
ans -= x.first;
pos[c]++;
//cout << x.first << "\n";
if ( pos[c] < opt[c].size() )
pq.push( { opt[c][pos[c]] - pos[c], c } );
d--;
}
cout << ans;
return 0;
}
Compilation message
prison.cpp: In function 'int main()':
prison.cpp:102:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | if ( pos[c] < opt[c].size() )
| ~~~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
103004 KB |
Output is correct |
2 |
Incorrect |
22 ms |
102996 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
103004 KB |
Output is correct |
2 |
Incorrect |
107 ms |
131620 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
103004 KB |
Output is correct |
2 |
Incorrect |
22 ms |
102996 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
103000 KB |
Output is correct |
2 |
Incorrect |
36 ms |
108588 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
103004 KB |
Output is correct |
2 |
Incorrect |
22 ms |
102996 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
103004 KB |
Output is correct |
2 |
Incorrect |
22 ms |
102996 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |