#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<long long,long long>pii;
inline int combine(int a, int b){
return max(a,b);
}
struct node{
int s,e,m;
node *l,*r;
int v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(0){
}
inline void inst(){
if(l==NULL)l=new node(s,m);
if(r==NULL)r=new node(m+1,e);
}
void upd(int x, int y){
if(s==e){
v=y;
return;
}
inst();
if(x<=m) l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
int query(int x, int y){
if(x<=s&&y>=e){
return v;
}
inst();
if(y<=m)return l->query(x,y);
if(x>m)return r->query(x,y);
return combine(l->query(x,m),r->query(m+1,y));
}
};
void solve(){
int n,k;
cin >> n >> k;
int maxn=1000000005;
node st(0,maxn);
int arr[n];
map<int,int>last;
for(int x=0;x<n;x++){
cin >> arr[x];
arr[x]++;
last[arr[x]]=-1;
}
int dp[n];
set<pii>se;
for(int x=0;x<n;x++){
//remove
while(!se.empty()){
if(se.begin()->first<x-k){
pii hold=*se.begin();
se.erase(se.begin());
st.upd(hold.second,0);
last[hold.second]=-1;
}
else break;
}
int l=st.query(0,arr[x]-1)+1;
int r=st.query(arr[x],maxn);
dp[x]=max(l,r);
st.upd(arr[x],l);
if(last[arr[x]]!=-1){
int index=last[arr[x]];
se.erase(se.find({index,arr[index]}));
}
last[arr[x]]=x;
se.insert({x,arr[x]});
}
cout << dp[n-1];
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
352 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
352 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
352 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
2792 KB |
Output is correct |
2 |
Incorrect |
177 ms |
2664 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
2656 KB |
Output is correct |
2 |
Correct |
237 ms |
2996 KB |
Output is correct |
3 |
Correct |
431 ms |
9496 KB |
Output is correct |
4 |
Correct |
1185 ms |
369328 KB |
Output is correct |
5 |
Correct |
985 ms |
369516 KB |
Output is correct |
6 |
Correct |
1148 ms |
368588 KB |
Output is correct |
7 |
Correct |
659 ms |
387780 KB |
Output is correct |
8 |
Correct |
642 ms |
387880 KB |
Output is correct |
9 |
Correct |
613 ms |
367644 KB |
Output is correct |
10 |
Correct |
840 ms |
368184 KB |
Output is correct |
11 |
Correct |
1230 ms |
369388 KB |
Output is correct |
12 |
Correct |
1132 ms |
369216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
352 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Incorrect |
1 ms |
360 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |