#include <bits/stdc++.h>
#define N 200005
using namespace std;
int t[N];
struct SegTree{
vector<int> t;
int n;
SegTree(int sz){
n = sz + 5;
t.assign(4*n,0);
}
void clear(){
t.assign(4*n,0);
}
void upd(int v,int tl,int tr,int pos,int val){
if(tl == tr){
t[v] = max(t[v],val);
return;
}
int tm = (tl + tr)/2;
if(pos <= tm)
upd(v*2,tl,tm,pos,val);
else upd(v*2+1,tm+1,tr,pos,val);
t[v] = max(t[v*2],t[v*2+1]);
}
int get(int v,int tl,int tr,int l,int r){
if(tr < l || r < tl)
return 0;
if(l <= tl && tr <= r){
return t[v];
}
int tm = (tl + tr)/2;
return max(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
}
void upd(int pos,int val){
upd(1,1,n,pos,val);
}
int get(int l,int r){
return get(1,1,n,l,r);
}
};
pair<int,int> sufquery[N];
pair<int,int> prequery[N];
int val[N][3];
void solve(){
int n,x;
cin >> n >> x;
int best = 0;
vector<pair<int,int>> compress;
for(int i = 1;i<=n;i++){
cin >> t[i];
compress.push_back({t[i],i});
compress.push_back({t[i]+x,i+n});
compress.push_back({t[i]-x,i+2*n});
}
sort(compress.begin(),compress.end());
int sz = compress.size();
int cnt = 0;
for(int i = 0;i<sz;i++){
if(i == 0 || compress[i].first != compress[i-1].first)
cnt++;
int x = compress[i].second;
int y = 0;
while(x > n){
x -= n;
y++;
}
val[x][y] = cnt+1;
}
SegTree tpre(sz);
SegTree tsuf(sz);
for(int i = 1;i<=n;i++){
int num = val[i][2];
tpre.upd(num,tpre.get(1,num-1)+1);
best = max(best,tpre.get(1,sz));
sufquery[i+1] = {tpre.get(num,num),num};
}
for(int i = n;i>=1;i--){
int num = val[i][1];
tsuf.upd(num,tsuf.get(num+1,sz)+1);
best = max(best,tsuf.get(1,sz));
prequery[i-1] = {tsuf.get(num,num),num};
}
tpre.clear();
tsuf.clear();
for(int i = 1;i<=n;i++){
int num = val[i][0];
tpre.upd(num,tpre.get(1,num-1)+1);
best = max(best,prequery[i].first + tpre.get(1,prequery[i].second-1));
}
for(int i = n;i>=1;i--){
int num = val[i][0];
tsuf.upd(num,tsuf.get(num+1,sz)+1);
best = max(best,sufquery[i].first + tsuf.get(sufquery[i].second+1,sz));
}
cout << best;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef Local
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while(t--){
solve();
}
#ifdef Local
cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds";
#endif
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
464 KB |
Output is correct |
22 |
Correct |
3 ms |
468 KB |
Output is correct |
23 |
Correct |
3 ms |
468 KB |
Output is correct |
24 |
Correct |
3 ms |
468 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
690 ms |
32124 KB |
Output is correct |
2 |
Correct |
661 ms |
32052 KB |
Output is correct |
3 |
Correct |
621 ms |
32124 KB |
Output is correct |
4 |
Correct |
592 ms |
32116 KB |
Output is correct |
5 |
Correct |
415 ms |
31292 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
8396 KB |
Output is correct |
2 |
Correct |
141 ms |
8396 KB |
Output is correct |
3 |
Correct |
142 ms |
8388 KB |
Output is correct |
4 |
Correct |
131 ms |
8156 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
107 ms |
8096 KB |
Output is correct |
7 |
Correct |
126 ms |
8404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
313 ms |
16316 KB |
Output is correct |
2 |
Correct |
293 ms |
16216 KB |
Output is correct |
3 |
Correct |
588 ms |
32124 KB |
Output is correct |
4 |
Correct |
420 ms |
31356 KB |
Output is correct |
5 |
Correct |
212 ms |
15808 KB |
Output is correct |
6 |
Correct |
395 ms |
29936 KB |
Output is correct |
7 |
Correct |
394 ms |
30692 KB |
Output is correct |
8 |
Correct |
243 ms |
16364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
328 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
464 KB |
Output is correct |
22 |
Correct |
3 ms |
468 KB |
Output is correct |
23 |
Correct |
3 ms |
468 KB |
Output is correct |
24 |
Correct |
3 ms |
468 KB |
Output is correct |
25 |
Correct |
2 ms |
468 KB |
Output is correct |
26 |
Correct |
2 ms |
460 KB |
Output is correct |
27 |
Correct |
690 ms |
32124 KB |
Output is correct |
28 |
Correct |
661 ms |
32052 KB |
Output is correct |
29 |
Correct |
621 ms |
32124 KB |
Output is correct |
30 |
Correct |
592 ms |
32116 KB |
Output is correct |
31 |
Correct |
415 ms |
31292 KB |
Output is correct |
32 |
Correct |
139 ms |
8396 KB |
Output is correct |
33 |
Correct |
141 ms |
8396 KB |
Output is correct |
34 |
Correct |
142 ms |
8388 KB |
Output is correct |
35 |
Correct |
131 ms |
8156 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
107 ms |
8096 KB |
Output is correct |
38 |
Correct |
126 ms |
8404 KB |
Output is correct |
39 |
Correct |
313 ms |
16316 KB |
Output is correct |
40 |
Correct |
293 ms |
16216 KB |
Output is correct |
41 |
Correct |
588 ms |
32124 KB |
Output is correct |
42 |
Correct |
420 ms |
31356 KB |
Output is correct |
43 |
Correct |
212 ms |
15808 KB |
Output is correct |
44 |
Correct |
395 ms |
29936 KB |
Output is correct |
45 |
Correct |
394 ms |
30692 KB |
Output is correct |
46 |
Correct |
243 ms |
16364 KB |
Output is correct |
47 |
Correct |
333 ms |
16268 KB |
Output is correct |
48 |
Correct |
286 ms |
16200 KB |
Output is correct |
49 |
Correct |
707 ms |
32132 KB |
Output is correct |
50 |
Correct |
448 ms |
31360 KB |
Output is correct |
51 |
Correct |
315 ms |
23636 KB |
Output is correct |
52 |
Correct |
476 ms |
31392 KB |
Output is correct |
53 |
Correct |
412 ms |
31460 KB |
Output is correct |
54 |
Correct |
478 ms |
32152 KB |
Output is correct |
55 |
Correct |
656 ms |
32152 KB |
Output is correct |