#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define eb emplace_back
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5, MAXN = 1e7 + 5;
const long long oo = 1e9 + 7, mod = 1e9 + 7;
int n, d;
ii a[N];
int IT[N << 2], dp[N];
set<ii> se;// segments with length >= d
bool out[N];
void upd(int id, int l, int r, int pos, int vl){
if(l == r){
IT[id] = vl;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) upd(id << 1, l, mid, pos, vl);
else upd(id << 1 | 1, mid + 1, r, pos, vl);
IT[id] = max(IT[id << 1], IT[id << 1 | 1]);
}
int get(int id, int l, int r, int L, int R){
if(l > R || r < L || l > r) return 0;
if(l >= L && r <= R) return IT[id];
int mid = (l + r) >> 1;
return max(get(id << 1, l, mid, L, R), get(id << 1 | 1, mid + 1, r, L, R));
}
bool cmp(ii a, ii b){
if(a.fi != b.fi) return a.fi < b.fi;
else return a.se > b.se;
}
void er(int temp){
out[temp] =1 ;
set<ii>::iterator it = se.lower_bound({temp, oo});
if(it != se.begin()){
//if(temp == 11) cout << temp << "\n";
it--;
ii tmp1 = (*it), tmp2 = {tmp1.fi, temp - 1}, tmp3 = {temp + 1, tmp1.se};
if(tmp1.se < temp || tmp1.fi > temp) return;
//if(temp == 11) cout << tmp1.fi << " " << tmp1.se << " " << temp << "\n";
se.erase(tmp1);
//cout << tmp2.fi << " " << tmp2.se << " " << tmp3.fi << " " << tmp3.se << "\n";
if((tmp2.se - tmp2.fi + 1) >= d){
//if(temp == 11) cout << tmp2.fi << " " << tmp2.se << "\n";
se.insert(tmp2);
}
if((tmp3.se - tmp3.fi + 1) >= d) se.insert(tmp3);
}
}
int saves[N];
void process(){
cin >> n >> d;
for(int i = 1; i <= n; i++){
cin >> a[i].fi;
a[i].se = i;
}
sort(a + 1, a + n + 1, cmp);
se.insert({1, n});
int ans = -1, itr = 1;
for(int i = 1; i <= n; i++){
//if(se.find({1, 11}) != se.end()) cout << i << "\n";
int temp = a[i].se;
//if(temp == 12) cout << out[11] << "\n";
while(itr <= n && a[itr].fi == a[i].fi){
er(a[itr].se);
itr++;
}
//cout << i << " " << itr << "\n";
//cout << i << "\n";
//for(auto it : se) cout << it.fi << " " << it.se << "\n";
int lst = 1;
set<ii>::iterator it = se.lower_bound({temp, oo});
if(it != se.begin()){
it--;
//if(temp == 12) cout << (*it).fi << " " << (*it).se << "\n";
lst = (*it).se + 1;
}
saves[temp] = lst;
//cout << i << " " << temp << " " << lst << "\n";
dp[temp] = get(1, 1, n, lst, temp - 1) + 1;
//cout << dp[temp] << "\n";
upd(1, 1, n, temp, dp[temp]);
ans = max(ans, dp[temp]);
}
//for(int i = 1; i <= n; i++) cout << i << " " << saves[i] << "\n";
cout << ans;
}
signed main(){
ios_base::sync_with_stdio(0);
#ifdef nqm
freopen("input.inp", "r", stdin);
freopen("output.out", "w", stdout);
#endif
#ifndef nqm
#endif
process();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
0 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
324 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
0 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
324 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
7 ms |
796 KB |
Output is correct |
42 |
Correct |
6 ms |
716 KB |
Output is correct |
43 |
Correct |
4 ms |
716 KB |
Output is correct |
44 |
Correct |
4 ms |
716 KB |
Output is correct |
45 |
Correct |
3 ms |
716 KB |
Output is correct |
46 |
Correct |
5 ms |
720 KB |
Output is correct |
47 |
Correct |
4 ms |
716 KB |
Output is correct |
48 |
Correct |
4 ms |
724 KB |
Output is correct |
49 |
Correct |
4 ms |
716 KB |
Output is correct |
50 |
Correct |
3 ms |
708 KB |
Output is correct |
51 |
Correct |
5 ms |
716 KB |
Output is correct |
52 |
Correct |
6 ms |
716 KB |
Output is correct |
53 |
Correct |
3 ms |
716 KB |
Output is correct |
54 |
Correct |
3 ms |
716 KB |
Output is correct |
55 |
Correct |
4 ms |
716 KB |
Output is correct |
56 |
Correct |
3 ms |
716 KB |
Output is correct |
57 |
Correct |
3 ms |
716 KB |
Output is correct |
58 |
Correct |
3 ms |
716 KB |
Output is correct |
59 |
Correct |
3 ms |
720 KB |
Output is correct |
60 |
Correct |
3 ms |
716 KB |
Output is correct |
61 |
Correct |
5 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
143 ms |
18368 KB |
Output is correct |
2 |
Correct |
243 ms |
23064 KB |
Output is correct |
3 |
Correct |
373 ms |
23068 KB |
Output is correct |
4 |
Correct |
455 ms |
23152 KB |
Output is correct |
5 |
Correct |
335 ms |
21800 KB |
Output is correct |
6 |
Correct |
448 ms |
23212 KB |
Output is correct |
7 |
Correct |
115 ms |
18304 KB |
Output is correct |
8 |
Correct |
114 ms |
18360 KB |
Output is correct |
9 |
Correct |
134 ms |
18452 KB |
Output is correct |
10 |
Correct |
142 ms |
18456 KB |
Output is correct |
11 |
Correct |
283 ms |
18580 KB |
Output is correct |
12 |
Correct |
324 ms |
19008 KB |
Output is correct |
13 |
Correct |
273 ms |
18656 KB |
Output is correct |
14 |
Correct |
393 ms |
18772 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
18372 KB |
Output is correct |
2 |
Correct |
217 ms |
18380 KB |
Output is correct |
3 |
Correct |
202 ms |
18456 KB |
Output is correct |
4 |
Correct |
195 ms |
18456 KB |
Output is correct |
5 |
Correct |
212 ms |
18372 KB |
Output is correct |
6 |
Correct |
200 ms |
18396 KB |
Output is correct |
7 |
Correct |
107 ms |
18440 KB |
Output is correct |
8 |
Correct |
142 ms |
18424 KB |
Output is correct |
9 |
Correct |
116 ms |
18380 KB |
Output is correct |
10 |
Correct |
149 ms |
18432 KB |
Output is correct |
11 |
Correct |
235 ms |
18384 KB |
Output is correct |
12 |
Correct |
164 ms |
18492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
324 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
0 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
332 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
332 KB |
Output is correct |
25 |
Correct |
0 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
0 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
0 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
324 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
7 ms |
796 KB |
Output is correct |
42 |
Correct |
6 ms |
716 KB |
Output is correct |
43 |
Correct |
4 ms |
716 KB |
Output is correct |
44 |
Correct |
4 ms |
716 KB |
Output is correct |
45 |
Correct |
3 ms |
716 KB |
Output is correct |
46 |
Correct |
5 ms |
720 KB |
Output is correct |
47 |
Correct |
4 ms |
716 KB |
Output is correct |
48 |
Correct |
4 ms |
724 KB |
Output is correct |
49 |
Correct |
4 ms |
716 KB |
Output is correct |
50 |
Correct |
3 ms |
708 KB |
Output is correct |
51 |
Correct |
5 ms |
716 KB |
Output is correct |
52 |
Correct |
6 ms |
716 KB |
Output is correct |
53 |
Correct |
3 ms |
716 KB |
Output is correct |
54 |
Correct |
3 ms |
716 KB |
Output is correct |
55 |
Correct |
4 ms |
716 KB |
Output is correct |
56 |
Correct |
3 ms |
716 KB |
Output is correct |
57 |
Correct |
3 ms |
716 KB |
Output is correct |
58 |
Correct |
3 ms |
716 KB |
Output is correct |
59 |
Correct |
3 ms |
720 KB |
Output is correct |
60 |
Correct |
3 ms |
716 KB |
Output is correct |
61 |
Correct |
5 ms |
716 KB |
Output is correct |
62 |
Correct |
143 ms |
18368 KB |
Output is correct |
63 |
Correct |
243 ms |
23064 KB |
Output is correct |
64 |
Correct |
373 ms |
23068 KB |
Output is correct |
65 |
Correct |
455 ms |
23152 KB |
Output is correct |
66 |
Correct |
335 ms |
21800 KB |
Output is correct |
67 |
Correct |
448 ms |
23212 KB |
Output is correct |
68 |
Correct |
115 ms |
18304 KB |
Output is correct |
69 |
Correct |
114 ms |
18360 KB |
Output is correct |
70 |
Correct |
134 ms |
18452 KB |
Output is correct |
71 |
Correct |
142 ms |
18456 KB |
Output is correct |
72 |
Correct |
283 ms |
18580 KB |
Output is correct |
73 |
Correct |
324 ms |
19008 KB |
Output is correct |
74 |
Correct |
273 ms |
18656 KB |
Output is correct |
75 |
Correct |
393 ms |
18772 KB |
Output is correct |
76 |
Correct |
117 ms |
18372 KB |
Output is correct |
77 |
Correct |
217 ms |
18380 KB |
Output is correct |
78 |
Correct |
202 ms |
18456 KB |
Output is correct |
79 |
Correct |
195 ms |
18456 KB |
Output is correct |
80 |
Correct |
212 ms |
18372 KB |
Output is correct |
81 |
Correct |
200 ms |
18396 KB |
Output is correct |
82 |
Correct |
107 ms |
18440 KB |
Output is correct |
83 |
Correct |
142 ms |
18424 KB |
Output is correct |
84 |
Correct |
116 ms |
18380 KB |
Output is correct |
85 |
Correct |
149 ms |
18432 KB |
Output is correct |
86 |
Correct |
235 ms |
18384 KB |
Output is correct |
87 |
Correct |
164 ms |
18492 KB |
Output is correct |
88 |
Correct |
404 ms |
23876 KB |
Output is correct |
89 |
Correct |
382 ms |
23108 KB |
Output is correct |
90 |
Correct |
282 ms |
21732 KB |
Output is correct |
91 |
Correct |
207 ms |
21092 KB |
Output is correct |
92 |
Correct |
172 ms |
21088 KB |
Output is correct |
93 |
Correct |
267 ms |
21072 KB |
Output is correct |
94 |
Correct |
203 ms |
21040 KB |
Output is correct |
95 |
Correct |
319 ms |
23236 KB |
Output is correct |
96 |
Correct |
293 ms |
21956 KB |
Output is correct |
97 |
Correct |
230 ms |
21316 KB |
Output is correct |
98 |
Correct |
211 ms |
21188 KB |
Output is correct |
99 |
Correct |
224 ms |
21220 KB |
Output is correct |
100 |
Correct |
194 ms |
20996 KB |
Output is correct |
101 |
Correct |
128 ms |
21072 KB |
Output is correct |
102 |
Correct |
121 ms |
21016 KB |
Output is correct |
103 |
Correct |
138 ms |
20968 KB |
Output is correct |
104 |
Correct |
153 ms |
21096 KB |
Output is correct |
105 |
Correct |
149 ms |
21056 KB |
Output is correct |
106 |
Correct |
181 ms |
21060 KB |
Output is correct |
107 |
Correct |
192 ms |
21092 KB |
Output is correct |
108 |
Correct |
191 ms |
21124 KB |
Output is correct |
109 |
Correct |
246 ms |
21100 KB |
Output is correct |
110 |
Correct |
213 ms |
21444 KB |
Output is correct |
111 |
Correct |
183 ms |
21164 KB |
Output is correct |
112 |
Correct |
173 ms |
21060 KB |
Output is correct |
113 |
Correct |
184 ms |
21060 KB |
Output is correct |
114 |
Correct |
183 ms |
21060 KB |
Output is correct |
115 |
Correct |
112 ms |
21060 KB |
Output is correct |
116 |
Correct |
110 ms |
21092 KB |
Output is correct |
117 |
Correct |
145 ms |
21084 KB |
Output is correct |
118 |
Correct |
152 ms |
21092 KB |
Output is correct |
119 |
Correct |
154 ms |
21096 KB |
Output is correct |
120 |
Correct |
171 ms |
21080 KB |
Output is correct |