#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:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,long long>pii;
typedef array<int,5>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
int arr[300005];
int n,k;
inline pi2 combine(pi2 a, pi2 b){
pi2 temp;
temp[0]=max(a[0],b[0]);
temp[3]=a[3]+b[3];
temp[1]=a[1];
if(a[1]==a[3]) temp[1]=a[3]+b[1];
temp[2]=b[2];
if(b[2]==b[3]) temp[2]=b[3]+a[2];
temp[4]=max({a[4],b[4],a[2]+b[1]});
return temp;
}
struct node{
int s,e,m;
node *l,*r;
pi2 v;
node(int ss, int ee):s(ss),e(ee),m((s+e)>>1){
v={0,0,0,e-s+1,0};
if(s!=e){
l=new node(s,m);
r=new node(m+1,e);
}
}
void upd(int x, int y){
if(s==e){
v[0]=y;
v[1]=v[2]=v[3]=v[4]=1;
return;
}
if(x<=m) l->upd(x,y);
else r->upd(x,y);
v=combine(l->v,r->v);
}
pi2 query(int x, int y){
if(x<=s&&y>=e){
return v;
}
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));
}
};
bool cmp(const pii a, const pii b){
if(a.first==b.first){
return a.second < b.second;
}
return a.first > b.first;
}
void solve(){
cin >> n >> k;
vector<pii>v;
for(int x=1;x<=n;x++){
cin >> arr[x];
v.push_back({arr[x],x});
}
sort(v.begin(),v.end(),cmp);
node st(0,n+5);
int dp[n+5];
memset(dp,0,sizeof(dp));
int ans=0;
for(int x=0;x<n;x++){
int index=v[x].second;
//show(index,index);
int l=index;
int r=n;
int best=n;
int mid;
while(l<=r){
mid=(l+r)/2;
pi2 hold=st.query(index,mid);
if(hold[4]>=k){
best=mid;
r=mid-1;
}
else l=mid+1;
}
dp[index]=max(dp[index],st.query(index,best)[0]+1);
ans=max(ans,dp[index]);
//show2(dp[index],dp[index],best,best);
st.upd(index,dp[index]);
}
cout << ans;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
int t=1;
//freopen("in.txt","r",stdin);
//cin >> t;
while(t--){
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 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 |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
424 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 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 |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
424 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
464 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 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 |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
424 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
464 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
14 ms |
1884 KB |
Output is correct |
42 |
Correct |
15 ms |
1880 KB |
Output is correct |
43 |
Correct |
12 ms |
2048 KB |
Output is correct |
44 |
Correct |
15 ms |
1860 KB |
Output is correct |
45 |
Correct |
14 ms |
1984 KB |
Output is correct |
46 |
Correct |
15 ms |
1884 KB |
Output is correct |
47 |
Correct |
12 ms |
2012 KB |
Output is correct |
48 |
Correct |
15 ms |
2380 KB |
Output is correct |
49 |
Correct |
14 ms |
1884 KB |
Output is correct |
50 |
Correct |
14 ms |
2080 KB |
Output is correct |
51 |
Correct |
12 ms |
1884 KB |
Output is correct |
52 |
Correct |
13 ms |
1884 KB |
Output is correct |
53 |
Correct |
10 ms |
2072 KB |
Output is correct |
54 |
Correct |
12 ms |
2068 KB |
Output is correct |
55 |
Correct |
15 ms |
1884 KB |
Output is correct |
56 |
Correct |
15 ms |
1880 KB |
Output is correct |
57 |
Correct |
15 ms |
2096 KB |
Output is correct |
58 |
Correct |
11 ms |
1884 KB |
Output is correct |
59 |
Correct |
11 ms |
2080 KB |
Output is correct |
60 |
Correct |
14 ms |
1880 KB |
Output is correct |
61 |
Correct |
13 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
904 ms |
66068 KB |
Output is correct |
2 |
Correct |
967 ms |
66996 KB |
Output is correct |
3 |
Correct |
1757 ms |
66744 KB |
Output is correct |
4 |
Correct |
2062 ms |
69436 KB |
Output is correct |
5 |
Correct |
1466 ms |
69816 KB |
Output is correct |
6 |
Correct |
2025 ms |
70568 KB |
Output is correct |
7 |
Correct |
748 ms |
69044 KB |
Output is correct |
8 |
Correct |
942 ms |
69044 KB |
Output is correct |
9 |
Correct |
775 ms |
69656 KB |
Output is correct |
10 |
Correct |
888 ms |
70328 KB |
Output is correct |
11 |
Correct |
1193 ms |
69812 KB |
Output is correct |
12 |
Correct |
1410 ms |
70716 KB |
Output is correct |
13 |
Correct |
1421 ms |
69304 KB |
Output is correct |
14 |
Correct |
2108 ms |
69560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
898 ms |
66568 KB |
Output is correct |
2 |
Correct |
1304 ms |
67256 KB |
Output is correct |
3 |
Correct |
1572 ms |
67512 KB |
Output is correct |
4 |
Correct |
1584 ms |
68020 KB |
Output is correct |
5 |
Correct |
1316 ms |
67000 KB |
Output is correct |
6 |
Correct |
1593 ms |
67512 KB |
Output is correct |
7 |
Correct |
919 ms |
66232 KB |
Output is correct |
8 |
Correct |
892 ms |
67252 KB |
Output is correct |
9 |
Correct |
952 ms |
65972 KB |
Output is correct |
10 |
Correct |
1202 ms |
67896 KB |
Output is correct |
11 |
Correct |
1583 ms |
66120 KB |
Output is correct |
12 |
Correct |
1298 ms |
67000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 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 |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
424 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
344 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
1 ms |
348 KB |
Output is correct |
24 |
Correct |
0 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
344 KB |
Output is correct |
28 |
Correct |
1 ms |
348 KB |
Output is correct |
29 |
Correct |
1 ms |
348 KB |
Output is correct |
30 |
Correct |
1 ms |
464 KB |
Output is correct |
31 |
Correct |
1 ms |
348 KB |
Output is correct |
32 |
Correct |
1 ms |
348 KB |
Output is correct |
33 |
Correct |
1 ms |
348 KB |
Output is correct |
34 |
Correct |
1 ms |
460 KB |
Output is correct |
35 |
Correct |
1 ms |
348 KB |
Output is correct |
36 |
Correct |
1 ms |
348 KB |
Output is correct |
37 |
Correct |
1 ms |
348 KB |
Output is correct |
38 |
Correct |
1 ms |
348 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
14 ms |
1884 KB |
Output is correct |
42 |
Correct |
15 ms |
1880 KB |
Output is correct |
43 |
Correct |
12 ms |
2048 KB |
Output is correct |
44 |
Correct |
15 ms |
1860 KB |
Output is correct |
45 |
Correct |
14 ms |
1984 KB |
Output is correct |
46 |
Correct |
15 ms |
1884 KB |
Output is correct |
47 |
Correct |
12 ms |
2012 KB |
Output is correct |
48 |
Correct |
15 ms |
2380 KB |
Output is correct |
49 |
Correct |
14 ms |
1884 KB |
Output is correct |
50 |
Correct |
14 ms |
2080 KB |
Output is correct |
51 |
Correct |
12 ms |
1884 KB |
Output is correct |
52 |
Correct |
13 ms |
1884 KB |
Output is correct |
53 |
Correct |
10 ms |
2072 KB |
Output is correct |
54 |
Correct |
12 ms |
2068 KB |
Output is correct |
55 |
Correct |
15 ms |
1884 KB |
Output is correct |
56 |
Correct |
15 ms |
1880 KB |
Output is correct |
57 |
Correct |
15 ms |
2096 KB |
Output is correct |
58 |
Correct |
11 ms |
1884 KB |
Output is correct |
59 |
Correct |
11 ms |
2080 KB |
Output is correct |
60 |
Correct |
14 ms |
1880 KB |
Output is correct |
61 |
Correct |
13 ms |
1884 KB |
Output is correct |
62 |
Correct |
904 ms |
66068 KB |
Output is correct |
63 |
Correct |
967 ms |
66996 KB |
Output is correct |
64 |
Correct |
1757 ms |
66744 KB |
Output is correct |
65 |
Correct |
2062 ms |
69436 KB |
Output is correct |
66 |
Correct |
1466 ms |
69816 KB |
Output is correct |
67 |
Correct |
2025 ms |
70568 KB |
Output is correct |
68 |
Correct |
748 ms |
69044 KB |
Output is correct |
69 |
Correct |
942 ms |
69044 KB |
Output is correct |
70 |
Correct |
775 ms |
69656 KB |
Output is correct |
71 |
Correct |
888 ms |
70328 KB |
Output is correct |
72 |
Correct |
1193 ms |
69812 KB |
Output is correct |
73 |
Correct |
1410 ms |
70716 KB |
Output is correct |
74 |
Correct |
1421 ms |
69304 KB |
Output is correct |
75 |
Correct |
2108 ms |
69560 KB |
Output is correct |
76 |
Correct |
898 ms |
66568 KB |
Output is correct |
77 |
Correct |
1304 ms |
67256 KB |
Output is correct |
78 |
Correct |
1572 ms |
67512 KB |
Output is correct |
79 |
Correct |
1584 ms |
68020 KB |
Output is correct |
80 |
Correct |
1316 ms |
67000 KB |
Output is correct |
81 |
Correct |
1593 ms |
67512 KB |
Output is correct |
82 |
Correct |
919 ms |
66232 KB |
Output is correct |
83 |
Correct |
892 ms |
67252 KB |
Output is correct |
84 |
Correct |
952 ms |
65972 KB |
Output is correct |
85 |
Correct |
1202 ms |
67896 KB |
Output is correct |
86 |
Correct |
1583 ms |
66120 KB |
Output is correct |
87 |
Correct |
1298 ms |
67000 KB |
Output is correct |
88 |
Correct |
2072 ms |
69248 KB |
Output is correct |
89 |
Correct |
2069 ms |
69812 KB |
Output is correct |
90 |
Correct |
1934 ms |
70464 KB |
Output is correct |
91 |
Correct |
1609 ms |
70408 KB |
Output is correct |
92 |
Correct |
1231 ms |
69556 KB |
Output is correct |
93 |
Correct |
1570 ms |
69936 KB |
Output is correct |
94 |
Correct |
1578 ms |
70980 KB |
Output is correct |
95 |
Correct |
1766 ms |
69556 KB |
Output is correct |
96 |
Correct |
1710 ms |
69868 KB |
Output is correct |
97 |
Correct |
1689 ms |
70480 KB |
Output is correct |
98 |
Correct |
1606 ms |
69044 KB |
Output is correct |
99 |
Correct |
1567 ms |
69132 KB |
Output is correct |
100 |
Correct |
1655 ms |
70332 KB |
Output is correct |
101 |
Correct |
774 ms |
70708 KB |
Output is correct |
102 |
Correct |
890 ms |
70328 KB |
Output is correct |
103 |
Correct |
997 ms |
70508 KB |
Output is correct |
104 |
Correct |
1141 ms |
69616 KB |
Output is correct |
105 |
Correct |
1327 ms |
70836 KB |
Output is correct |
106 |
Correct |
1136 ms |
70732 KB |
Output is correct |
107 |
Correct |
1379 ms |
70872 KB |
Output is correct |
108 |
Correct |
1729 ms |
71104 KB |
Output is correct |
109 |
Correct |
1340 ms |
70144 KB |
Output is correct |
110 |
Correct |
1759 ms |
69320 KB |
Output is correct |
111 |
Correct |
1693 ms |
70052 KB |
Output is correct |
112 |
Correct |
1287 ms |
70168 KB |
Output is correct |
113 |
Correct |
1592 ms |
70932 KB |
Output is correct |
114 |
Correct |
1692 ms |
69920 KB |
Output is correct |
115 |
Correct |
942 ms |
68992 KB |
Output is correct |
116 |
Correct |
897 ms |
70072 KB |
Output is correct |
117 |
Correct |
973 ms |
70332 KB |
Output is correct |
118 |
Correct |
1040 ms |
69644 KB |
Output is correct |
119 |
Correct |
1260 ms |
69812 KB |
Output is correct |
120 |
Correct |
1333 ms |
69388 KB |
Output is correct |