#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
void fastio() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
const int N = 3e5+5;
const int MOD = 1e9+7;
const int INF = 1e12;
const int M = 1e6+5;
const long double EPS = 0.00001;
int n,m,q,d;
vector<int> dp, b;
vector<array<int,2> > a;
queue<array<int,2> > ques[N];
vector<int> vis(N, 0);
struct SegTree {
int sz;
vector<int> data;
SegTree(int sz) {
this->sz = sz;
data.assign(4*(sz + 2), -INF);
}
void update(int tl, int tr ,int v, int ind, int val) {
if(tl == tr) {
data[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if(ind <= tm) {
update(tl, tm, v*2, ind, val);
}
else {
update(tm + 1, tr, v*2+1, ind, val);
}
data[v] = max(data[v*2], data[v*2+1]);
}
void update(int ind ,int val) {
update(0, sz, 1, ind ,val);
}
int query(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) return data[v];
if(tl > r || tr < l) {
return -INF;
}
int tm = (tl + tr) >> 1;
return max(query(tl, tm, v*2, l, r) , query(tm + 1, tr, v*2+1, l, r));
}
int query(int l, int r) {
return query(0, sz, 1, l, r);
}
};
struct IndexedSeg {
int sz;
vector<array<int,2> > data;
IndexedSeg(int sz) {
this->sz = sz;
data.assign(4*(sz + 2), {-INF, -INF});
}
void update(int tl, int tr ,int v, int ind, int val) {
if(tl == tr) {
data[v] = {val, tl};
return;
}
int tm = (tl + tr) >> 1;
if(ind <= tm) {
update(tl, tm, v*2, ind, val);
}
else {
update(tm + 1, tr, v*2+1, ind, val);
}
data[v] = max(data[v*2], data[v*2+1]);
}
void update(int ind ,int val) {
update(0, sz, 1, ind ,val);
}
array<int,2> query(int tl, int tr, int v, int l, int r) {
if(tl >= l && tr <= r) return data[v];
if(tl > r || tr < l) {
return {-INF, -INF};
}
int tm = (tl + tr) >> 1;
return max(query(tl, tm, v*2, l, r) , query(tm + 1, tr, v*2+1, l, r));
}
array<int,2> query(int l, int r) {
return query(0, sz, 1, l, r);
}
};
void operate(SegTree &st, int ind ,int order) {
while(ques[ind].size() && ques[ind].front()[0] <= dp[order]) {
ques[ind].pop();
}
ques[ind].push({dp[order], order});
st.update(ind, ques[ind].front()[0]);
}
void remove_el(SegTree &st, int ind) {
while(ques[ind].size() && vis[ ques[ind].front()[1] ]) {
ques[ind].pop();
}
if(ques[ind].size()) {
st.update(ind, ques[ind].front()[0]);
}
else {
st.update(ind, -INF);
}
}
void compress() {
sort(a.begin(), a.end());
int last = -1;
int cur = 0;
for(int i = 0; i<n; i++) {
if(a[i][0] == last) {
a[i][0] = cur;
}
else {
last = a[i][0];
cur++;
a[i][0] = cur;
}
}
b.assign(n+1, 0);
for(auto c : a) {
b[c[1]] = c[0];
}
}
signed main() {
fastio();
cin>>n>>d;
a.resize(n);
dp.assign(n + 1, 1);
REP(i,n) {
cin>>a[i][0];
a[i][1] = i + 1;
}
compress();
SegTree stmain(n + 5);
IndexedSeg stsec(n + 5);
dp[n] = 1;
operate(stmain, b[n], n);
stsec.update(n, -b[n]);
for(int i = n - 1; i>=1; i--) {
dp[i] = stmain.query(b[i] + 1, n + 3) + 1;
dp[i] = max(dp[i] , 1ll);
operate(stmain, b[i], i);
if(i + d <= n) {
array<int,2> last = stsec.query(i + d, n+2);
last[0] = abs(last[0]);
while(last[0] <= b[i]) {
vis[last[1]] = 1;
remove_el(stmain, b[last[1]]);
stsec.update(last[1], -INF);
last = stsec.query(i + d, n+2);
last[0] = abs(last[0]);
}
}
stsec.update(i, -b[i]);
}
int ans = 0;
for(int i = 1 ;i<=n;i++) {
ans = max(ans , dp[i]);
}
cout<<ans<<"\n";
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:8:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
| ^
Main.cpp:148:5: note: in expansion of macro 'REP'
148 | REP(i,n) {
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
204884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
204884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
204884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
204884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
