/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n, a[N], d, idx[N], DP[N];
vector<int> val, S[N];
void merg(int x, int y){
if(S[x].size() > S[y].size()){
for(auto p: S[y]) S[x].pb(p);
S[x].swap(S[y]);
S[x].clear();
}else{
for(auto p: S[x]) S[y].pb(p);
S[x].clear();
}
}
void solve(){
cin >> n >> d;
for(int i = 1; i <= n; ++i){
cin >> a[i];
val.pb(a[i]);
}
sort(all(val));
val.erase(unique(all(val)), val.end());
for(int i = 1; i <= n; ++i) a[i] = lower_bound(all(val), a[i]) - val.begin() + 1;
for(int i = 1; i <= n; ++i) idx[i] = -1, DP[i] = 0;
idx[n] = n;
DP[n] = 1;
multiset<pair<int, int>> si, dp;
dp.insert({a[n], n});
si.insert({a[n], n});
S[n].pb(n);
int ans = 1;
for(int i = n - 1; i >= 1; --i){
int r = i + d + 1;
if(r <= n && idx[r] != -1){
si.erase({a[r], r});
for(auto k: S[r]){
auto it = dp.find({a[k], k});
if(it != dp.end()) dp.erase(it);
}
}
idx[i] = i;
S[i].pb(i);
while(!si.empty() && (*prev(si.end())).first >= a[i]){
auto x = (*prev(si.end())).second;
si.erase(prev(si.end()));
idx[x] = -1;
merg(x, i);
}
auto it = dp.upper_bound(pair<int, int>{a[i], MOD});
DP[i] = (it == dp.end() ? 1 : DP[(*it).second] + 1);
dp.insert({a[i], i});
it = dp.lower_bound(pair<int,int>{a[i], i});
while(it != dp.begin() && DP[(*prev(it)).second] <= DP[i]){
dp.erase(prev(it));
it = dp.lower_bound(pair<int,int>{a[i], i});
}
if(next(it) != dp.end() && DP[(*next(it)).second] == DP[i]){
dp.erase(it);
}
ans = max(ans, DP[(*dp.begin()).second]);
// for(auto k: dp) cout << k.first << ' ' << k.second << ' ' << DP[k.second] << " | ";
// en;
}
cout << ans;
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
// en;
en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:87:15: warning: unused variable 'aa' [-Wunused-variable]
87 | int tt = 1, aa;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
9 ms |
29276 KB |
Output is correct |
5 |
Correct |
8 ms |
29276 KB |
Output is correct |
6 |
Correct |
8 ms |
29272 KB |
Output is correct |
7 |
Correct |
8 ms |
29276 KB |
Output is correct |
8 |
Correct |
8 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
8 ms |
29276 KB |
Output is correct |
11 |
Correct |
8 ms |
29276 KB |
Output is correct |
12 |
Correct |
8 ms |
29276 KB |
Output is correct |
13 |
Correct |
8 ms |
29276 KB |
Output is correct |
14 |
Correct |
8 ms |
29272 KB |
Output is correct |
15 |
Incorrect |
9 ms |
29276 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
9 ms |
29276 KB |
Output is correct |
5 |
Correct |
8 ms |
29276 KB |
Output is correct |
6 |
Correct |
8 ms |
29272 KB |
Output is correct |
7 |
Correct |
8 ms |
29276 KB |
Output is correct |
8 |
Correct |
8 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
8 ms |
29276 KB |
Output is correct |
11 |
Correct |
8 ms |
29276 KB |
Output is correct |
12 |
Correct |
8 ms |
29276 KB |
Output is correct |
13 |
Correct |
8 ms |
29276 KB |
Output is correct |
14 |
Correct |
8 ms |
29272 KB |
Output is correct |
15 |
Incorrect |
9 ms |
29276 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
9 ms |
29276 KB |
Output is correct |
5 |
Correct |
8 ms |
29276 KB |
Output is correct |
6 |
Correct |
8 ms |
29272 KB |
Output is correct |
7 |
Correct |
8 ms |
29276 KB |
Output is correct |
8 |
Correct |
8 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
8 ms |
29276 KB |
Output is correct |
11 |
Correct |
8 ms |
29276 KB |
Output is correct |
12 |
Correct |
8 ms |
29276 KB |
Output is correct |
13 |
Correct |
8 ms |
29276 KB |
Output is correct |
14 |
Correct |
8 ms |
29272 KB |
Output is correct |
15 |
Incorrect |
9 ms |
29276 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
39904 KB |
Output is correct |
2 |
Incorrect |
76 ms |
39880 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
68 ms |
39912 KB |
Output is correct |
2 |
Correct |
115 ms |
39880 KB |
Output is correct |
3 |
Correct |
154 ms |
39884 KB |
Output is correct |
4 |
Correct |
183 ms |
39900 KB |
Output is correct |
5 |
Correct |
192 ms |
45256 KB |
Output is correct |
6 |
Correct |
185 ms |
39880 KB |
Output is correct |
7 |
Correct |
174 ms |
54212 KB |
Output is correct |
8 |
Correct |
82 ms |
39864 KB |
Output is correct |
9 |
Correct |
128 ms |
43720 KB |
Output is correct |
10 |
Correct |
147 ms |
40060 KB |
Output is correct |
11 |
Correct |
176 ms |
40176 KB |
Output is correct |
12 |
Correct |
113 ms |
39932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
29276 KB |
Output is correct |
2 |
Correct |
7 ms |
29276 KB |
Output is correct |
3 |
Correct |
8 ms |
29276 KB |
Output is correct |
4 |
Correct |
9 ms |
29276 KB |
Output is correct |
5 |
Correct |
8 ms |
29276 KB |
Output is correct |
6 |
Correct |
8 ms |
29272 KB |
Output is correct |
7 |
Correct |
8 ms |
29276 KB |
Output is correct |
8 |
Correct |
8 ms |
29276 KB |
Output is correct |
9 |
Correct |
8 ms |
29276 KB |
Output is correct |
10 |
Correct |
8 ms |
29276 KB |
Output is correct |
11 |
Correct |
8 ms |
29276 KB |
Output is correct |
12 |
Correct |
8 ms |
29276 KB |
Output is correct |
13 |
Correct |
8 ms |
29276 KB |
Output is correct |
14 |
Correct |
8 ms |
29272 KB |
Output is correct |
15 |
Incorrect |
9 ms |
29276 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |