#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,k;
int arr[200005];
int fw[200005];
int bw[200005];
struct node{
int s,e,m;
int val=0;
node *l,*r;
node(int _s,int _e){
s=_s,e=_e,m=(s+e)>>1; //going to lazily build the ST
if (s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void update(int i,int j){
if (s==e){
val=j;
}
else{
if (i<=m) l->update(i,j);
else if (m<i) r->update(i,j);
val=max(l->val,r->val);
}
}
int query(int i,int j){
if (i==s && j==e) return val;
else if (j<=m) return l->query(i,j);
else if (m<i) return r->query(i,j);
else return max(l->query(i,m),r->query(m+1,j));
}
}*root=new node(0,200005);
int main(){
scanf("%d%d",&n,&k);
for (int x=0;x<n;x++) scanf("%d",&arr[x]);
vector<int> v;
vector<int>::iterator it;
v.push_back(arr[0]);
fw[0]=1;
for (int x=1;x<n;x++){
if (v.back()<arr[x]){
v.push_back(arr[x]);
fw[x]=v.size();
}
else{
it=lower_bound(v.begin(),v.end(),arr[x]);
v[it-v.begin()]=arr[x];
fw[x]=it-v.begin()+1;
}
}
v.clear();
v.push_back(-arr[n-1]);
bw[n-1]=1;
for (int x=n-2;x>=0;x--){
if (v.back()<-arr[x]) {
v.push_back(-arr[x]);
bw[x]=v.size();
}
else{
it=lower_bound(v.begin(),v.end(),-arr[x]);
v[it-v.begin()]=-arr[x];
bw[x]=it-v.begin()+1;
}
}
//for (int x=0;x<n;x++) printf("%d %d\n",fw[x],bw[x]);
v.clear();
for (int x=0;x<n;x++) v.push_back(x);
sort(v.begin(),v.end(),[](int i,int j){
return arr[i]>arr[j];
});
it=v.begin();
int ans=-1;
for (int x=0;x<n;x++){
while (it!=v.end() && arr[v[x]]<arr[*it]+k) root->update(*it,bw[*it]),it++;
ans=max(ans,fw[v[x]]+root->query(v[x]+1,n));
}
printf("%d\n",ans);
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&k);
~~~~~^~~~~~~~~~~~~~
glo.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int x=0;x<n;x++) scanf("%d",&arr[x]);
~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
19192 KB |
Output is correct |
2 |
Correct |
30 ms |
19064 KB |
Output is correct |
3 |
Correct |
29 ms |
19064 KB |
Output is correct |
4 |
Correct |
30 ms |
19192 KB |
Output is correct |
5 |
Correct |
30 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19064 KB |
Output is correct |
7 |
Correct |
29 ms |
19192 KB |
Output is correct |
8 |
Correct |
29 ms |
19064 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19192 KB |
Output is correct |
11 |
Correct |
28 ms |
19036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
19192 KB |
Output is correct |
2 |
Correct |
30 ms |
19064 KB |
Output is correct |
3 |
Correct |
29 ms |
19064 KB |
Output is correct |
4 |
Correct |
30 ms |
19192 KB |
Output is correct |
5 |
Correct |
30 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19064 KB |
Output is correct |
7 |
Correct |
29 ms |
19192 KB |
Output is correct |
8 |
Correct |
29 ms |
19064 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19192 KB |
Output is correct |
11 |
Correct |
28 ms |
19036 KB |
Output is correct |
12 |
Correct |
29 ms |
19064 KB |
Output is correct |
13 |
Correct |
28 ms |
19192 KB |
Output is correct |
14 |
Correct |
28 ms |
19192 KB |
Output is correct |
15 |
Correct |
30 ms |
19128 KB |
Output is correct |
16 |
Correct |
30 ms |
19036 KB |
Output is correct |
17 |
Correct |
29 ms |
19064 KB |
Output is correct |
18 |
Correct |
29 ms |
19164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
19192 KB |
Output is correct |
2 |
Correct |
30 ms |
19064 KB |
Output is correct |
3 |
Correct |
29 ms |
19064 KB |
Output is correct |
4 |
Correct |
30 ms |
19192 KB |
Output is correct |
5 |
Correct |
30 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19064 KB |
Output is correct |
7 |
Correct |
29 ms |
19192 KB |
Output is correct |
8 |
Correct |
29 ms |
19064 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19192 KB |
Output is correct |
11 |
Correct |
28 ms |
19036 KB |
Output is correct |
12 |
Correct |
29 ms |
19064 KB |
Output is correct |
13 |
Correct |
28 ms |
19192 KB |
Output is correct |
14 |
Correct |
28 ms |
19192 KB |
Output is correct |
15 |
Correct |
30 ms |
19128 KB |
Output is correct |
16 |
Correct |
30 ms |
19036 KB |
Output is correct |
17 |
Correct |
29 ms |
19064 KB |
Output is correct |
18 |
Correct |
29 ms |
19164 KB |
Output is correct |
19 |
Correct |
30 ms |
19192 KB |
Output is correct |
20 |
Correct |
30 ms |
19192 KB |
Output is correct |
21 |
Correct |
29 ms |
19196 KB |
Output is correct |
22 |
Correct |
30 ms |
19064 KB |
Output is correct |
23 |
Correct |
29 ms |
19164 KB |
Output is correct |
24 |
Correct |
28 ms |
19192 KB |
Output is correct |
25 |
Correct |
54 ms |
19156 KB |
Output is correct |
26 |
Correct |
29 ms |
19192 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
318 ms |
24568 KB |
Output is correct |
2 |
Correct |
300 ms |
24304 KB |
Output is correct |
3 |
Correct |
304 ms |
24560 KB |
Output is correct |
4 |
Correct |
306 ms |
24560 KB |
Output is correct |
5 |
Correct |
179 ms |
23792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
20600 KB |
Output is correct |
2 |
Correct |
86 ms |
20604 KB |
Output is correct |
3 |
Correct |
83 ms |
20600 KB |
Output is correct |
4 |
Correct |
60 ms |
20344 KB |
Output is correct |
5 |
Correct |
29 ms |
19068 KB |
Output is correct |
6 |
Correct |
56 ms |
20344 KB |
Output is correct |
7 |
Correct |
69 ms |
20572 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
171 ms |
21848 KB |
Output is correct |
2 |
Correct |
253 ms |
22004 KB |
Output is correct |
3 |
Correct |
367 ms |
24560 KB |
Output is correct |
4 |
Correct |
195 ms |
23792 KB |
Output is correct |
5 |
Correct |
87 ms |
21492 KB |
Output is correct |
6 |
Correct |
133 ms |
23664 KB |
Output is correct |
7 |
Correct |
140 ms |
24304 KB |
Output is correct |
8 |
Correct |
124 ms |
21876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
30 ms |
19192 KB |
Output is correct |
2 |
Correct |
30 ms |
19064 KB |
Output is correct |
3 |
Correct |
29 ms |
19064 KB |
Output is correct |
4 |
Correct |
30 ms |
19192 KB |
Output is correct |
5 |
Correct |
30 ms |
19192 KB |
Output is correct |
6 |
Correct |
29 ms |
19064 KB |
Output is correct |
7 |
Correct |
29 ms |
19192 KB |
Output is correct |
8 |
Correct |
29 ms |
19064 KB |
Output is correct |
9 |
Correct |
29 ms |
19192 KB |
Output is correct |
10 |
Correct |
29 ms |
19192 KB |
Output is correct |
11 |
Correct |
28 ms |
19036 KB |
Output is correct |
12 |
Correct |
29 ms |
19064 KB |
Output is correct |
13 |
Correct |
28 ms |
19192 KB |
Output is correct |
14 |
Correct |
28 ms |
19192 KB |
Output is correct |
15 |
Correct |
30 ms |
19128 KB |
Output is correct |
16 |
Correct |
30 ms |
19036 KB |
Output is correct |
17 |
Correct |
29 ms |
19064 KB |
Output is correct |
18 |
Correct |
29 ms |
19164 KB |
Output is correct |
19 |
Correct |
30 ms |
19192 KB |
Output is correct |
20 |
Correct |
30 ms |
19192 KB |
Output is correct |
21 |
Correct |
29 ms |
19196 KB |
Output is correct |
22 |
Correct |
30 ms |
19064 KB |
Output is correct |
23 |
Correct |
29 ms |
19164 KB |
Output is correct |
24 |
Correct |
28 ms |
19192 KB |
Output is correct |
25 |
Correct |
54 ms |
19156 KB |
Output is correct |
26 |
Correct |
29 ms |
19192 KB |
Output is correct |
27 |
Correct |
318 ms |
24568 KB |
Output is correct |
28 |
Correct |
300 ms |
24304 KB |
Output is correct |
29 |
Correct |
304 ms |
24560 KB |
Output is correct |
30 |
Correct |
306 ms |
24560 KB |
Output is correct |
31 |
Correct |
179 ms |
23792 KB |
Output is correct |
32 |
Correct |
81 ms |
20600 KB |
Output is correct |
33 |
Correct |
86 ms |
20604 KB |
Output is correct |
34 |
Correct |
83 ms |
20600 KB |
Output is correct |
35 |
Correct |
60 ms |
20344 KB |
Output is correct |
36 |
Correct |
29 ms |
19068 KB |
Output is correct |
37 |
Correct |
56 ms |
20344 KB |
Output is correct |
38 |
Correct |
69 ms |
20572 KB |
Output is correct |
39 |
Correct |
171 ms |
21848 KB |
Output is correct |
40 |
Correct |
253 ms |
22004 KB |
Output is correct |
41 |
Correct |
367 ms |
24560 KB |
Output is correct |
42 |
Correct |
195 ms |
23792 KB |
Output is correct |
43 |
Correct |
87 ms |
21492 KB |
Output is correct |
44 |
Correct |
133 ms |
23664 KB |
Output is correct |
45 |
Correct |
140 ms |
24304 KB |
Output is correct |
46 |
Correct |
124 ms |
21876 KB |
Output is correct |
47 |
Correct |
206 ms |
21844 KB |
Output is correct |
48 |
Correct |
161 ms |
21876 KB |
Output is correct |
49 |
Correct |
345 ms |
24560 KB |
Output is correct |
50 |
Correct |
175 ms |
23792 KB |
Output is correct |
51 |
Correct |
126 ms |
22896 KB |
Output is correct |
52 |
Correct |
146 ms |
23920 KB |
Output is correct |
53 |
Correct |
148 ms |
23920 KB |
Output is correct |
54 |
Correct |
154 ms |
24556 KB |
Output is correct |
55 |
Correct |
224 ms |
24556 KB |
Output is correct |