This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define dl double
using namespace std;
const int N = 1e6 + 7;
const long long mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int p[N];
int get(int x)
{
return (p[x] == x ? x : p[x] = get(p[x]));
}
void meg(int x, int y)
{
x = get(x);
y = get(y);
p[y] = x;
}
void solve()
{
int n,D;
cin >> n >> D;
vector<int> a(n + 1, 0);
vector<int> id;
for(int i = 1; i <= n; i++){
cin >> a[i];
id.push_back(i);
p[i] = i;
}
sort(id.begin(), id.end(), [&](int i, int j){
return a[i] < a[j];
});
vector<int> d(n + 1, 0);
for(int i = 0; i < n; i++){
int j = i;
vector<int> g;
while(j < n && a[id[i]] == a[id[j]]){
int x = id[j];
int mx = 1;
int id = -1;
for(int h = x; h >= max(1, x - D); h--){
if(d[h] > 0){
id = get(h);
break;
}
}
for(int h = x; h >= 1; h--){
if(get(h) == id)mx = max(mx, d[h] + 1);
}
g.push_back(mx);
j++;
}
for(int h = i; h < j; h++){
d[id[h]] = g[h - i];
}
for(int h = i; h < j; h++){
int st = id[h];
for(int g = max(1, st - D); g <= min(n, st + D); g++){
if(d[g] > 0){
meg(st, g);
}
}
}
i = j - 1;
}
cout << *max_element(d.begin(), d.end());
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |