#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;
const int N=3e5;
struct sagiri
{
vector<int> st;
sagiri()
{
st.resize(N*4, 0);
}
void mdf(int i,int l,int r,int p,int x)
{
int m=l+(r-l)/2;
if(l==r)
{
st[i]=x;
return;
}
if(p<=m)
mdf(i*2,l,m,p,x);
else
mdf(i*2+1,m+1,r,p,x);
st[i]=max(st[i*2], st[i*2+1]);
}
int qry(int i,int l,int r,int L,int R)
{
int m=l+(r-l)/2;
if(L<=l && r<=R)
return st[i];
else if(R<=m)
return qry(i*2,l,m,L,R);
else if(L>m)
return qry(i*2+1,m+1,r,L,R);
else
return max(qry(i*2,l,m,L,r), qry(i*2+1,m+1,r,L,R) );
}
}dis, dp;
void solve()
{
int n,d;
cin>>n>>d;
vector<matsuri> arr;
for(int i=1;i<=n;i++)
{
int a;
cin>>a;
arr.emplace_back(a,-i);
}
sort(arr.begin(), arr.end());
set<int> s;
dp.mdf(1,0,n,0,0);
s.insert(0);
dis.mdf(1,0,n,0,n);
int ii=0;
for(auto [a,i]:arr)
{
i*=-1;
while(ii<n && arr[ii].first==a)
{
//cout<<ii<<'\n';
int j=arr[ii++].second*-1;
s.insert(j);
auto it=s.find(j);
it--;
dis.mdf(1,0,n,*it,j-*it);
//cout<<" . "<<*it<<' '<<j<<'\n';
it=s.upper_bound(j);
if(it==s.end())
dis.mdf(1,0,n,j,n-j);
else
dis.mdf(1,0,n,j,*it-j);
}
int l=0, r=i;
//cout<<i<<' '<<a<<'\n';
while(l<r)
{
int m=l+(r-l)/2;
//cout<<" - "<<m<<' '<<dis.qry(1,0,n,m,i-1)<<'\n';
//for(int j=m;j<=i;j++)
// cout<<" "<<dis.qry(1,0,n,j,j)<<'\n';
if(dis.qry(1,0,n,m,i-1)<=d)
r=m;
else
l=m+1;
}
//cout<<' '<<l<<' '<<i<<' '<<dp.qry(1,0,n,l,i)<<'\n';
dp.mdf(1,0,n,i,dp.qry(1,0,n,l,i)+1);
}
cout<<dp.qry(1,0,n,0,n)<<'\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
//cin>>T;
while(T--)
solve();
return 0;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:64:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | for(auto [a,i]:arr)
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
19036 KB |
Output is correct |
2 |
Correct |
6 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19032 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19036 KB |
Output is correct |
6 |
Correct |
4 ms |
19252 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19032 KB |
Output is correct |
10 |
Correct |
4 ms |
19292 KB |
Output is correct |
11 |
Correct |
4 ms |
19036 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
19036 KB |
Output is correct |
16 |
Correct |
5 ms |
19144 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
19036 KB |
Output is correct |
19 |
Correct |
4 ms |
19036 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
4 ms |
19036 KB |
Output is correct |
22 |
Correct |
5 ms |
19036 KB |
Output is correct |
23 |
Correct |
5 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
6 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
19036 KB |
Output is correct |
2 |
Correct |
6 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19032 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19036 KB |
Output is correct |
6 |
Correct |
4 ms |
19252 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19032 KB |
Output is correct |
10 |
Correct |
4 ms |
19292 KB |
Output is correct |
11 |
Correct |
4 ms |
19036 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
19036 KB |
Output is correct |
16 |
Correct |
5 ms |
19144 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
19036 KB |
Output is correct |
19 |
Correct |
4 ms |
19036 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
4 ms |
19036 KB |
Output is correct |
22 |
Correct |
5 ms |
19036 KB |
Output is correct |
23 |
Correct |
5 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
6 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Correct |
4 ms |
19036 KB |
Output is correct |
28 |
Correct |
5 ms |
19032 KB |
Output is correct |
29 |
Correct |
5 ms |
19036 KB |
Output is correct |
30 |
Correct |
4 ms |
19036 KB |
Output is correct |
31 |
Correct |
4 ms |
19036 KB |
Output is correct |
32 |
Correct |
5 ms |
19036 KB |
Output is correct |
33 |
Correct |
4 ms |
19272 KB |
Output is correct |
34 |
Correct |
5 ms |
19036 KB |
Output is correct |
35 |
Correct |
5 ms |
19036 KB |
Output is correct |
36 |
Correct |
5 ms |
19036 KB |
Output is correct |
37 |
Correct |
4 ms |
19276 KB |
Output is correct |
38 |
Correct |
4 ms |
19036 KB |
Output is correct |
39 |
Correct |
5 ms |
19036 KB |
Output is correct |
40 |
Correct |
4 ms |
19036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
19036 KB |
Output is correct |
2 |
Correct |
6 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19032 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19036 KB |
Output is correct |
6 |
Correct |
4 ms |
19252 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19032 KB |
Output is correct |
10 |
Correct |
4 ms |
19292 KB |
Output is correct |
11 |
Correct |
4 ms |
19036 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
19036 KB |
Output is correct |
16 |
Correct |
5 ms |
19144 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
19036 KB |
Output is correct |
19 |
Correct |
4 ms |
19036 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
4 ms |
19036 KB |
Output is correct |
22 |
Correct |
5 ms |
19036 KB |
Output is correct |
23 |
Correct |
5 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
6 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Correct |
4 ms |
19036 KB |
Output is correct |
28 |
Correct |
5 ms |
19032 KB |
Output is correct |
29 |
Correct |
5 ms |
19036 KB |
Output is correct |
30 |
Correct |
4 ms |
19036 KB |
Output is correct |
31 |
Correct |
4 ms |
19036 KB |
Output is correct |
32 |
Correct |
5 ms |
19036 KB |
Output is correct |
33 |
Correct |
4 ms |
19272 KB |
Output is correct |
34 |
Correct |
5 ms |
19036 KB |
Output is correct |
35 |
Correct |
5 ms |
19036 KB |
Output is correct |
36 |
Correct |
5 ms |
19036 KB |
Output is correct |
37 |
Correct |
4 ms |
19276 KB |
Output is correct |
38 |
Correct |
4 ms |
19036 KB |
Output is correct |
39 |
Correct |
5 ms |
19036 KB |
Output is correct |
40 |
Correct |
4 ms |
19036 KB |
Output is correct |
41 |
Correct |
18 ms |
19608 KB |
Output is correct |
42 |
Correct |
17 ms |
19548 KB |
Output is correct |
43 |
Correct |
15 ms |
19536 KB |
Output is correct |
44 |
Correct |
16 ms |
19544 KB |
Output is correct |
45 |
Correct |
18 ms |
19548 KB |
Output is correct |
46 |
Correct |
18 ms |
19548 KB |
Output is correct |
47 |
Correct |
16 ms |
19544 KB |
Output is correct |
48 |
Correct |
17 ms |
19548 KB |
Output is correct |
49 |
Correct |
18 ms |
19496 KB |
Output is correct |
50 |
Correct |
18 ms |
19548 KB |
Output is correct |
51 |
Correct |
17 ms |
19560 KB |
Output is correct |
52 |
Correct |
18 ms |
19596 KB |
Output is correct |
53 |
Correct |
15 ms |
19648 KB |
Output is correct |
54 |
Correct |
16 ms |
19548 KB |
Output is correct |
55 |
Correct |
19 ms |
19804 KB |
Output is correct |
56 |
Correct |
18 ms |
19496 KB |
Output is correct |
57 |
Correct |
20 ms |
19544 KB |
Output is correct |
58 |
Correct |
14 ms |
19544 KB |
Output is correct |
59 |
Correct |
14 ms |
19548 KB |
Output is correct |
60 |
Correct |
17 ms |
19548 KB |
Output is correct |
61 |
Correct |
16 ms |
19500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
792 ms |
38076 KB |
Output is correct |
2 |
Correct |
839 ms |
39140 KB |
Output is correct |
3 |
Correct |
1134 ms |
38356 KB |
Output is correct |
4 |
Correct |
1341 ms |
40264 KB |
Output is correct |
5 |
Correct |
1115 ms |
39728 KB |
Output is correct |
6 |
Correct |
1340 ms |
39940 KB |
Output is correct |
7 |
Correct |
800 ms |
39324 KB |
Output is correct |
8 |
Correct |
827 ms |
39240 KB |
Output is correct |
9 |
Correct |
785 ms |
38840 KB |
Output is correct |
10 |
Correct |
821 ms |
38056 KB |
Output is correct |
11 |
Correct |
991 ms |
39104 KB |
Output is correct |
12 |
Correct |
1029 ms |
39360 KB |
Output is correct |
13 |
Correct |
1169 ms |
38084 KB |
Output is correct |
14 |
Correct |
1279 ms |
38448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
790 ms |
40036 KB |
Output is correct |
2 |
Correct |
1002 ms |
40964 KB |
Output is correct |
3 |
Correct |
1182 ms |
41656 KB |
Output is correct |
4 |
Correct |
1265 ms |
42728 KB |
Output is correct |
5 |
Correct |
1083 ms |
42136 KB |
Output is correct |
6 |
Correct |
1213 ms |
42836 KB |
Output is correct |
7 |
Correct |
808 ms |
41640 KB |
Output is correct |
8 |
Correct |
803 ms |
42768 KB |
Output is correct |
9 |
Correct |
807 ms |
41912 KB |
Output is correct |
10 |
Correct |
1014 ms |
41268 KB |
Output is correct |
11 |
Correct |
1245 ms |
41520 KB |
Output is correct |
12 |
Correct |
1131 ms |
41404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
19036 KB |
Output is correct |
2 |
Correct |
6 ms |
19036 KB |
Output is correct |
3 |
Correct |
5 ms |
19032 KB |
Output is correct |
4 |
Correct |
4 ms |
19036 KB |
Output is correct |
5 |
Correct |
5 ms |
19036 KB |
Output is correct |
6 |
Correct |
4 ms |
19252 KB |
Output is correct |
7 |
Correct |
4 ms |
19036 KB |
Output is correct |
8 |
Correct |
4 ms |
19036 KB |
Output is correct |
9 |
Correct |
4 ms |
19032 KB |
Output is correct |
10 |
Correct |
4 ms |
19292 KB |
Output is correct |
11 |
Correct |
4 ms |
19036 KB |
Output is correct |
12 |
Correct |
4 ms |
19036 KB |
Output is correct |
13 |
Correct |
4 ms |
19036 KB |
Output is correct |
14 |
Correct |
4 ms |
19036 KB |
Output is correct |
15 |
Correct |
4 ms |
19036 KB |
Output is correct |
16 |
Correct |
5 ms |
19144 KB |
Output is correct |
17 |
Correct |
5 ms |
19036 KB |
Output is correct |
18 |
Correct |
4 ms |
19036 KB |
Output is correct |
19 |
Correct |
4 ms |
19036 KB |
Output is correct |
20 |
Correct |
4 ms |
19036 KB |
Output is correct |
21 |
Correct |
4 ms |
19036 KB |
Output is correct |
22 |
Correct |
5 ms |
19036 KB |
Output is correct |
23 |
Correct |
5 ms |
19036 KB |
Output is correct |
24 |
Correct |
4 ms |
19036 KB |
Output is correct |
25 |
Correct |
6 ms |
19036 KB |
Output is correct |
26 |
Correct |
4 ms |
19036 KB |
Output is correct |
27 |
Correct |
4 ms |
19036 KB |
Output is correct |
28 |
Correct |
5 ms |
19032 KB |
Output is correct |
29 |
Correct |
5 ms |
19036 KB |
Output is correct |
30 |
Correct |
4 ms |
19036 KB |
Output is correct |
31 |
Correct |
4 ms |
19036 KB |
Output is correct |
32 |
Correct |
5 ms |
19036 KB |
Output is correct |
33 |
Correct |
4 ms |
19272 KB |
Output is correct |
34 |
Correct |
5 ms |
19036 KB |
Output is correct |
35 |
Correct |
5 ms |
19036 KB |
Output is correct |
36 |
Correct |
5 ms |
19036 KB |
Output is correct |
37 |
Correct |
4 ms |
19276 KB |
Output is correct |
38 |
Correct |
4 ms |
19036 KB |
Output is correct |
39 |
Correct |
5 ms |
19036 KB |
Output is correct |
40 |
Correct |
4 ms |
19036 KB |
Output is correct |
41 |
Correct |
18 ms |
19608 KB |
Output is correct |
42 |
Correct |
17 ms |
19548 KB |
Output is correct |
43 |
Correct |
15 ms |
19536 KB |
Output is correct |
44 |
Correct |
16 ms |
19544 KB |
Output is correct |
45 |
Correct |
18 ms |
19548 KB |
Output is correct |
46 |
Correct |
18 ms |
19548 KB |
Output is correct |
47 |
Correct |
16 ms |
19544 KB |
Output is correct |
48 |
Correct |
17 ms |
19548 KB |
Output is correct |
49 |
Correct |
18 ms |
19496 KB |
Output is correct |
50 |
Correct |
18 ms |
19548 KB |
Output is correct |
51 |
Correct |
17 ms |
19560 KB |
Output is correct |
52 |
Correct |
18 ms |
19596 KB |
Output is correct |
53 |
Correct |
15 ms |
19648 KB |
Output is correct |
54 |
Correct |
16 ms |
19548 KB |
Output is correct |
55 |
Correct |
19 ms |
19804 KB |
Output is correct |
56 |
Correct |
18 ms |
19496 KB |
Output is correct |
57 |
Correct |
20 ms |
19544 KB |
Output is correct |
58 |
Correct |
14 ms |
19544 KB |
Output is correct |
59 |
Correct |
14 ms |
19548 KB |
Output is correct |
60 |
Correct |
17 ms |
19548 KB |
Output is correct |
61 |
Correct |
16 ms |
19500 KB |
Output is correct |
62 |
Correct |
792 ms |
38076 KB |
Output is correct |
63 |
Correct |
839 ms |
39140 KB |
Output is correct |
64 |
Correct |
1134 ms |
38356 KB |
Output is correct |
65 |
Correct |
1341 ms |
40264 KB |
Output is correct |
66 |
Correct |
1115 ms |
39728 KB |
Output is correct |
67 |
Correct |
1340 ms |
39940 KB |
Output is correct |
68 |
Correct |
800 ms |
39324 KB |
Output is correct |
69 |
Correct |
827 ms |
39240 KB |
Output is correct |
70 |
Correct |
785 ms |
38840 KB |
Output is correct |
71 |
Correct |
821 ms |
38056 KB |
Output is correct |
72 |
Correct |
991 ms |
39104 KB |
Output is correct |
73 |
Correct |
1029 ms |
39360 KB |
Output is correct |
74 |
Correct |
1169 ms |
38084 KB |
Output is correct |
75 |
Correct |
1279 ms |
38448 KB |
Output is correct |
76 |
Correct |
790 ms |
40036 KB |
Output is correct |
77 |
Correct |
1002 ms |
40964 KB |
Output is correct |
78 |
Correct |
1182 ms |
41656 KB |
Output is correct |
79 |
Correct |
1265 ms |
42728 KB |
Output is correct |
80 |
Correct |
1083 ms |
42136 KB |
Output is correct |
81 |
Correct |
1213 ms |
42836 KB |
Output is correct |
82 |
Correct |
808 ms |
41640 KB |
Output is correct |
83 |
Correct |
803 ms |
42768 KB |
Output is correct |
84 |
Correct |
807 ms |
41912 KB |
Output is correct |
85 |
Correct |
1014 ms |
41268 KB |
Output is correct |
86 |
Correct |
1245 ms |
41520 KB |
Output is correct |
87 |
Correct |
1131 ms |
41404 KB |
Output is correct |
88 |
Correct |
1189 ms |
42176 KB |
Output is correct |
89 |
Correct |
1241 ms |
42048 KB |
Output is correct |
90 |
Correct |
1284 ms |
42744 KB |
Output is correct |
91 |
Correct |
1241 ms |
42536 KB |
Output is correct |
92 |
Correct |
971 ms |
42432 KB |
Output is correct |
93 |
Correct |
1179 ms |
41692 KB |
Output is correct |
94 |
Correct |
1269 ms |
41116 KB |
Output is correct |
95 |
Correct |
1120 ms |
42940 KB |
Output is correct |
96 |
Correct |
1204 ms |
42596 KB |
Output is correct |
97 |
Correct |
1270 ms |
42424 KB |
Output is correct |
98 |
Correct |
1285 ms |
42500 KB |
Output is correct |
99 |
Correct |
1223 ms |
42004 KB |
Output is correct |
100 |
Correct |
1226 ms |
42312 KB |
Output is correct |
101 |
Correct |
839 ms |
41596 KB |
Output is correct |
102 |
Correct |
826 ms |
42820 KB |
Output is correct |
103 |
Correct |
888 ms |
41884 KB |
Output is correct |
104 |
Correct |
973 ms |
41776 KB |
Output is correct |
105 |
Correct |
1059 ms |
41500 KB |
Output is correct |
106 |
Correct |
998 ms |
42004 KB |
Output is correct |
107 |
Correct |
1062 ms |
42688 KB |
Output is correct |
108 |
Correct |
1189 ms |
42176 KB |
Output is correct |
109 |
Correct |
1084 ms |
42120 KB |
Output is correct |
110 |
Correct |
1234 ms |
41956 KB |
Output is correct |
111 |
Correct |
1241 ms |
42340 KB |
Output is correct |
112 |
Correct |
1038 ms |
41744 KB |
Output is correct |
113 |
Correct |
1237 ms |
42636 KB |
Output is correct |
114 |
Correct |
1246 ms |
43056 KB |
Output is correct |
115 |
Correct |
810 ms |
40936 KB |
Output is correct |
116 |
Correct |
821 ms |
42428 KB |
Output is correct |
117 |
Correct |
873 ms |
42500 KB |
Output is correct |
118 |
Correct |
861 ms |
41932 KB |
Output is correct |
119 |
Correct |
988 ms |
42372 KB |
Output is correct |
120 |
Correct |
981 ms |
41372 KB |
Output is correct |