이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define dl double
using namespace std;
const int N = 3e5 + 7;
const long long mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int p[N];
int t[4 * 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;
}
int get(int x, int l, int r, int tl, int tr)
{
if(tl > tr)return 0;
if(l == tl && r == tr){
return t[x];
}
int m = (l + r) / 2;
return max(get(x + x, l, m, tl, min(tr, m)),
get(x + x + 1, m + 1, r, max(tl, m + 1), tr));
}
void upd(int x, int l, int r, int pos, int val)
{
if(l == r){
t[x] = val;
return;
}
int m = (l + r) / 2;
if(pos <= m)upd(x + x, l, m, pos, val);
else upd(x + x + 1, m + 1, r, pos, val);
t[x] = max(t[x + x], t[x + x + 1]);
}
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);
set<int> s;
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;
auto gg = s.lower_bound(x);
if(!s.empty() && gg != s.begin()){
gg--;
if(x - *gg <= D)id = get(*gg);
}
if(id == -1){
g.push_back(1);
j++;
continue;
}
int l = 1, r = id;
while(l < r){
int m = (l + r) / 2;
gg = s.lower_bound(m);
if(get(*gg) == id)r = m;
else l = m + 1;
}
mx = get(1, 1, n, l, x) + 1;
g.push_back(mx);
j++;
}
for(int h = i; h < j; h++){
d[id[h]] = g[h - i];
s.insert(id[h]);
upd(1, 1, n, id[h], d[id[h]]);
}
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... |