#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10;
long long n,k,t,inf=1e9+5;
int all[maxn],res=0;
vector<pair<int,int>>allq;
set<int>alld[maxn];
void vorod(){
cin>>n>>k>>t;
for(int i=1;i<=n;i++){
cin>>all[i];
}
}
void calbaz(){
all[0]=inf;
vector<int>v;
v.push_back(0);
for(int i=1;i<=n;i++){
while((int)v.size()>0&&all[v.back()]+(i-v.back())>=all[i]){
v.pop_back();
}
while((int)v.size()>0&&all[v.back()]+(i-v.back())>t){
v.pop_back();
}
if(all[i]>t){
if((int)v.size()==0){
res++;
}else{
allq.push_back(make_pair(v.back(),i-1));
}
}
v.push_back(i);
}
}
void aval(){
for(int i=0;i<allq.size();i++){
for(int j=allq[i].first;j<=allq[i].second;j++){
alld[j].insert(i);
}
}
}
void pre(){
calbaz();
aval();
}
int getmx(){
int wh=-1,mn=0;
for(int i=1;i<=n;i++){
if((int)alld[i].size()>mn){
mn=(int)alld[i].size();
wh=i;
}
}
return wh;
}
void remove(int ind){
if(ind==-1){
return ;
}
res+=(int)alld[ind].size();
set<int>hey=alld[ind];
for(auto x:hey){
for(int j=allq[x].first;j<=allq[x].second;j++){
alld[j].erase(x);
}
}
}
void cal(){
int ind=getmx();
remove(ind);
}
void solve(){
for(int i=0;i<k;i++){
cal();
}
}
void khor(){
res=n-res;
cout<<res<<"\n";
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("inp.txt","r",stdin);
vorod();
pre();
solve();
khor();
}
Compilation message
prison.cpp: In function 'void aval()':
prison.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<allq.size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94804 KB |
Output is correct |
2 |
Correct |
25 ms |
94948 KB |
Output is correct |
3 |
Correct |
25 ms |
95036 KB |
Output is correct |
4 |
Correct |
27 ms |
95028 KB |
Output is correct |
5 |
Correct |
30 ms |
95068 KB |
Output is correct |
6 |
Correct |
26 ms |
95968 KB |
Output is correct |
7 |
Correct |
26 ms |
95100 KB |
Output is correct |
8 |
Correct |
25 ms |
95028 KB |
Output is correct |
9 |
Correct |
26 ms |
95324 KB |
Output is correct |
10 |
Correct |
28 ms |
95580 KB |
Output is correct |
11 |
Correct |
26 ms |
95068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
94808 KB |
Output is correct |
2 |
Correct |
118 ms |
126452 KB |
Output is correct |
3 |
Correct |
87 ms |
114552 KB |
Output is correct |
4 |
Execution timed out |
2073 ms |
369292 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94804 KB |
Output is correct |
2 |
Correct |
25 ms |
94948 KB |
Output is correct |
3 |
Correct |
25 ms |
95036 KB |
Output is correct |
4 |
Correct |
27 ms |
95028 KB |
Output is correct |
5 |
Correct |
30 ms |
95068 KB |
Output is correct |
6 |
Correct |
26 ms |
95968 KB |
Output is correct |
7 |
Correct |
26 ms |
95100 KB |
Output is correct |
8 |
Correct |
25 ms |
95028 KB |
Output is correct |
9 |
Correct |
26 ms |
95324 KB |
Output is correct |
10 |
Correct |
28 ms |
95580 KB |
Output is correct |
11 |
Correct |
26 ms |
95068 KB |
Output is correct |
12 |
Correct |
25 ms |
94808 KB |
Output is correct |
13 |
Correct |
25 ms |
95056 KB |
Output is correct |
14 |
Correct |
26 ms |
95024 KB |
Output is correct |
15 |
Correct |
26 ms |
95064 KB |
Output is correct |
16 |
Correct |
26 ms |
95064 KB |
Output is correct |
17 |
Correct |
27 ms |
95920 KB |
Output is correct |
18 |
Correct |
27 ms |
95068 KB |
Output is correct |
19 |
Correct |
25 ms |
95068 KB |
Output is correct |
20 |
Correct |
26 ms |
95320 KB |
Output is correct |
21 |
Correct |
26 ms |
95324 KB |
Output is correct |
22 |
Correct |
27 ms |
95068 KB |
Output is correct |
23 |
Correct |
27 ms |
95320 KB |
Output is correct |
24 |
Correct |
26 ms |
95068 KB |
Output is correct |
25 |
Correct |
27 ms |
95324 KB |
Output is correct |
26 |
Correct |
32 ms |
95312 KB |
Output is correct |
27 |
Correct |
27 ms |
95324 KB |
Output is correct |
28 |
Correct |
26 ms |
95320 KB |
Output is correct |
29 |
Correct |
26 ms |
95320 KB |
Output is correct |
30 |
Correct |
38 ms |
98140 KB |
Output is correct |
31 |
Correct |
44 ms |
100180 KB |
Output is correct |
32 |
Correct |
27 ms |
95568 KB |
Output is correct |
33 |
Correct |
31 ms |
96348 KB |
Output is correct |
34 |
Correct |
32 ms |
98652 KB |
Output is correct |
35 |
Correct |
137 ms |
114988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
94812 KB |
Output is correct |
2 |
Correct |
41 ms |
101760 KB |
Output is correct |
3 |
Correct |
38 ms |
99536 KB |
Output is correct |
4 |
Execution timed out |
2111 ms |
353768 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94804 KB |
Output is correct |
2 |
Correct |
25 ms |
94948 KB |
Output is correct |
3 |
Correct |
25 ms |
95036 KB |
Output is correct |
4 |
Correct |
27 ms |
95028 KB |
Output is correct |
5 |
Correct |
30 ms |
95068 KB |
Output is correct |
6 |
Correct |
26 ms |
95968 KB |
Output is correct |
7 |
Correct |
26 ms |
95100 KB |
Output is correct |
8 |
Correct |
25 ms |
95028 KB |
Output is correct |
9 |
Correct |
26 ms |
95324 KB |
Output is correct |
10 |
Correct |
28 ms |
95580 KB |
Output is correct |
11 |
Correct |
26 ms |
95068 KB |
Output is correct |
12 |
Correct |
25 ms |
94808 KB |
Output is correct |
13 |
Correct |
25 ms |
95056 KB |
Output is correct |
14 |
Correct |
26 ms |
95024 KB |
Output is correct |
15 |
Correct |
26 ms |
95064 KB |
Output is correct |
16 |
Correct |
26 ms |
95064 KB |
Output is correct |
17 |
Correct |
27 ms |
95920 KB |
Output is correct |
18 |
Correct |
27 ms |
95068 KB |
Output is correct |
19 |
Correct |
25 ms |
95068 KB |
Output is correct |
20 |
Correct |
26 ms |
95320 KB |
Output is correct |
21 |
Correct |
26 ms |
95324 KB |
Output is correct |
22 |
Correct |
27 ms |
95068 KB |
Output is correct |
23 |
Correct |
27 ms |
95320 KB |
Output is correct |
24 |
Correct |
26 ms |
95068 KB |
Output is correct |
25 |
Correct |
27 ms |
95324 KB |
Output is correct |
26 |
Correct |
32 ms |
95312 KB |
Output is correct |
27 |
Correct |
27 ms |
95324 KB |
Output is correct |
28 |
Correct |
26 ms |
95320 KB |
Output is correct |
29 |
Correct |
26 ms |
95320 KB |
Output is correct |
30 |
Correct |
38 ms |
98140 KB |
Output is correct |
31 |
Correct |
44 ms |
100180 KB |
Output is correct |
32 |
Correct |
27 ms |
95568 KB |
Output is correct |
33 |
Correct |
31 ms |
96348 KB |
Output is correct |
34 |
Correct |
32 ms |
98652 KB |
Output is correct |
35 |
Correct |
137 ms |
114988 KB |
Output is correct |
36 |
Correct |
24 ms |
94812 KB |
Output is correct |
37 |
Correct |
41 ms |
101760 KB |
Output is correct |
38 |
Correct |
38 ms |
99536 KB |
Output is correct |
39 |
Execution timed out |
2111 ms |
353768 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
94804 KB |
Output is correct |
2 |
Correct |
25 ms |
94948 KB |
Output is correct |
3 |
Correct |
25 ms |
95036 KB |
Output is correct |
4 |
Correct |
27 ms |
95028 KB |
Output is correct |
5 |
Correct |
30 ms |
95068 KB |
Output is correct |
6 |
Correct |
26 ms |
95968 KB |
Output is correct |
7 |
Correct |
26 ms |
95100 KB |
Output is correct |
8 |
Correct |
25 ms |
95028 KB |
Output is correct |
9 |
Correct |
26 ms |
95324 KB |
Output is correct |
10 |
Correct |
28 ms |
95580 KB |
Output is correct |
11 |
Correct |
26 ms |
95068 KB |
Output is correct |
12 |
Correct |
26 ms |
94808 KB |
Output is correct |
13 |
Correct |
118 ms |
126452 KB |
Output is correct |
14 |
Correct |
87 ms |
114552 KB |
Output is correct |
15 |
Execution timed out |
2073 ms |
369292 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |