#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
using namespace std;
const int N = 3e5 + 10;
int a[N],dp[N],st[N * 4];
void modify(int node,int tl,int tr,int index,int val) {
if(tl > index || tr < index) return;
if(tl == tr) {
st[node] = max(st[node],val);
return;
}
int mid = (tl + tr) / 2;
modify(node * 2,tl,mid,index,val);
modify(node * 2 + 1,mid + 1,tr,index,val);
st[node] = max(st[node * 2],st[node * 2 + 1]);
}
int get(int node,int tl,int tr,int l,int r) {
if(l > r) return 0;
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r) return st[node];
int mid = (tl + tr) / 2;
return max(get(node * 2,tl,mid,l,r),get(node * 2 + 1,mid + 1,tr,l,r));
}
bool cmp(pair<int,int>A,pair<int,int>B) {
if(A.F == B.F) return A.S < B.S;
return A.F < B.F;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*int n,d;
cin >> n >> d;
for(int i = 1; i <= n; i++) {
cin >> a[i];
dp[i] = 1;
}
vector<pair<int,int>>vec;
for(int i = 1; i <= n; i++) vec.pb({a[i],i});
sort(vec.begin(),vec.end(),cmp);
vector<pair<int,int>>updates; // update pos dpval
for(int i = 0; i < n; i++) {
if(i > 0 && vec[i].F != vec[i - 1].F) {
for(auto X : updates) modify(1,1,n,X.F,X.S);
updates.clear();
}
int j = max(1ll,vec[i].S - d);
updates.pb({vec[i].S,get(1,1,n,j,vec[i].S - 1) + 1});
}
for(auto X : updates) modify(1,1,n,X.F,X.S);
cout << get(1,1,n,1,n);*/
int n,d;
cin >> n >> d;
for(int i = 1; i <= n; i++) {
cin >> a[i];
dp[i] = 1;
}
for(int i = 1; i <= n; i++) {
for(int j = i - 1; j >= 1; j--) {
if(i - j > d) break;
if(a[i] > a[j]) dp[i] = max(dp[i],dp[j] + 1);
}
}
int res = 0;
for(int i = 1; i <= n; i++) res = max(res,dp[i]);
cout << res;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
23 ms |
6164 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
6128 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
4035 ms |
5916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 13 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 14 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 15 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 16 |
Halted |
0 ms |
0 KB |
- |
