#include <bits/stdc++.h>
#define DIMN 2000010
using namespace std;
int v[DIMN] , w[DIMN] , f[DIMN] , out[DIMN] , mark[DIMN] , tt[DIMN] , closest[DIMN];
pair <int , int> ev[2 * DIMN] , idk[DIMN];
priority_queue <int> h;
priority_queue <pair <int , int> > h2;
pair <int , int> cnt[DIMN];
vector <int> g[DIMN];
void dfs (int nod){
int i , vecin;
cnt[nod] = make_pair(1 , nod);
for (i = 0 ; i < g[nod].size() ; i++){
vecin = g[nod][i];
dfs(vecin);
if (cnt[vecin].first + 1 > cnt[nod].first){
cnt[nod] = make_pair(cnt[vecin].first + 1 , cnt[vecin].second);
}
}
}
int main()
{
FILE *fin = stdin;
FILE *fout = stdout;
int n , d , t , sol , i , elem = 0 , e = 0 , pmax , j , now = 0 , nod , vecin;
fscanf (fin,"%d%d%d",&n,&d,&t);
sol = 0;
now = 0;
for (i = 1 ; i <= n ; i++){
fscanf (fin,"%d",&v[i]);
if (v[i] > t){
closest[i] = now;
w[++elem] = i;
now = i;
}
else sol++;
}
for (i = 1 ; i <= n ; i++){
if (v[i] < t){
/// cauti in w intervalul de influenta
pmax = min(n , i + t - v[i]);
ev[++e] = make_pair(i , i);
ev[++e] = make_pair(pmax + 1 , -i);
}
}
sort (ev + 1 , ev + e + 1);
i = 1;
j = 1;
while (j <= elem){
while (i <= e && ev[i].first <= w[j]){
/// procesezi ev[i]
if (ev[i].second > 0)
h.push(ev[i].second);
else {
out[-ev[i].second] = 1; /// il scoti
}
i++;
}
/// acum vezi w[j] ce tata are
while (!h.empty() && out[h.top()])
h.pop();
if (!h.empty()){
if (closest[w[j]] < h.top()){
g[0].push_back(w[j]); /// j nu e legat de alt elem > t
//printf ("0 %d\n" , w[j]);
tt[w[j]] = 0;
}
else {
g[w[j]].push_back(closest[w[j]]);
//printf ("%d %d\n" , w[j] , closest[w[j]]);
tt[closest[w[j]]] = w[j];
}
}
j++;
}
/// acum avem un arbore cu radacina fictiva 0
/// daca sterg un nod, se sterge tot drumul de la el la 0
/// sterg d noduri a.i sa ramana nr minim de noduri in arb
dfs (0);
for (i = 0 ; i < g[0].size() ; i++){
nod = g[0][i];
h2.push(cnt[nod]);
}
mark[0] = 1;
for (j = 1 ; j <= d ; j++){
while (mark[h2.top().second])
h2.pop();
nod = h2.top().second;
h2.pop();
while (!mark[nod]){
mark[nod] = 1;
for (i = 0 ; i < g[tt[nod]].size() ; i++){
vecin = g[tt[nod]][i];
if (!mark[vecin])
h2.push(cnt[vecin]);
}
nod = tt[nod];
}
}
for (i = 1 ; i <= n ; i++){
if (v[i] > t && !mark[i])
sol++;
}
fprintf (fout,"%d",sol);
return 0;
}
Compilation message
prison.cpp: In function 'void dfs(int)':
prison.cpp:14:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (i = 0 ; i < g[nod].size() ; i++){
| ~~^~~~~~~~~~~~~~~
prison.cpp: In function 'int main()':
prison.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (i = 0 ; i < g[0].size() ; i++){
| ~~^~~~~~~~~~~~~
prison.cpp:122:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (i = 0 ; i < g[tt[nod]].size() ; i++){
| ~~^~~~~~~~~~~~~~~~~~~
prison.cpp:29:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | fscanf (fin,"%d%d%d",&n,&d,&t);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
prison.cpp:33:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
33 | fscanf (fin,"%d",&v[i]);
| ~~~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47320 KB |
Output is correct |
2 |
Incorrect |
26 ms |
47316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
47312 KB |
Output is correct |
2 |
Incorrect |
180 ms |
76448 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47320 KB |
Output is correct |
2 |
Incorrect |
26 ms |
47316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
47228 KB |
Output is correct |
2 |
Incorrect |
54 ms |
55432 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47320 KB |
Output is correct |
2 |
Incorrect |
26 ms |
47316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
47320 KB |
Output is correct |
2 |
Incorrect |
26 ms |
47316 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |