#include <bits/stdc++.h>
using namespace std;
struct stree
{
int st[600100];
int N;
void init(vector<int>arr)
{
N=arr.size();
int i;
for(i=0;i<N;i++)
st[i+N]=arr[i];
for(i=N-1;i>0;i--)
st[i]=max(st[i<<1],st[i<<1|1]);
}
void upd(int n,int k)
{
st[N+n]=k;
for(n+=N;n>1;n>>=1)
{
st[n>>1]=max(st[n],st[n^1]);
}
}
int q(int l,int r,int mi)
{
int ans=mi;
l+=N;
r+=N;
for(;l<r;l>>=1,r>>=1)
{
if(l&1)
ans=max(ans,st[l++]);
if(r&1)
ans=max(ans,st[--r]);
}
return ans;
}
}val,cma,dp;
string s[3];
int lim[300100];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N,M;
cin >> N >> M;
int i;
vector<pair<int,int>>x;
vector<int>arr;
vector<int>da(N,0);
dp.init(da);
for(i=0;i<N;i++)
{
int a;
cin >> a;
x.push_back({-a,i});
arr.push_back(a);
}
sort(x.begin(),x.end());
val.init(arr);
vector<int>su;
for(i=0;i<N-M;i++)
{
su.push_back(val.q(i,i+M+1,0));
}
cma.init(su);
for(i=0;i<N;i++)
{
if(i>=su.size()+2)
{
lim[i]=N;
continue;
}
int s=i+1;
int e=su.size();
while(s<e)
{
int m=(s+e)>>1;
if(cma.q(i+1,m+1,0)<=arr[i])
s=m+1;
else
e=m;
}
lim[i]=e+M;
}
int ans=0;
for(i=0;i<N;i++)
{
int va=dp.q(x[i].second+1,lim[x[i].second],0)+1;
ans=max(ans,va);
dp.upd(x[i].second,va);
}
cout << ans;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:70:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | if(i>=su.size()+2)
| ~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
515 ms |
16428 KB |
Output is correct |
2 |
Incorrect |
440 ms |
16360 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
12840 KB |
Output is correct |
2 |
Correct |
150 ms |
12880 KB |
Output is correct |
3 |
Correct |
139 ms |
12880 KB |
Output is correct |
4 |
Correct |
137 ms |
12928 KB |
Output is correct |
5 |
Correct |
125 ms |
12984 KB |
Output is correct |
6 |
Correct |
130 ms |
12936 KB |
Output is correct |
7 |
Correct |
84 ms |
12904 KB |
Output is correct |
8 |
Correct |
80 ms |
12896 KB |
Output is correct |
9 |
Correct |
89 ms |
12884 KB |
Output is correct |
10 |
Correct |
114 ms |
12864 KB |
Output is correct |
11 |
Correct |
130 ms |
12888 KB |
Output is correct |
12 |
Correct |
110 ms |
13048 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
1 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 |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Incorrect |
0 ms |
332 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |