이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define f first
#define s second
#define FAST ios_base::sync_with_stdio(0); cin.tie(0);
#define all(x) x.begin(),x.end()
typedef pair<int, pi> pii;
const int maxn = 200010;
const int INF = LLONG_MAX/2;
const int mod = 1e9+7;
int n, X;
struct node {
int s,m,e,v;
node *l, *r;
node (int _s, int _e) {
s = _s; e = _e; m = (s+e)/2;
v = 0;
if (s != e) {
l = new node(s,m);
r = new node(m+1,e);
}
}
void up(int x, int newv) {
if (s == e) v = max(v,newv);
else {
if (x <= m) l -> up(x,newv);
else r -> up(x,newv);
v = max(l -> v, r -> v);
}
}
int rmq(int x, int y) {
if (x == s and e == y) return v;
if (x > m) return r -> rmq(x,y);
else if (y <= m) return l -> rmq(x,y);
else return max(l -> rmq(x,m), r -> rmq(m+1,y));
}
}*root;
int best[maxn];
int suf;
int32_t main() {
//FAST
cin >> n >> X;
vector <int> v(n);
for (int i =0;i<n;i++) {
cin >> v[i];
}
vector <int> vv = v;
sort(all(vv));
root = new node(0,n-1);
vector <int> lis;
for (int i =0;i<n;i++) {
int x = v[i];
if (lis.empty() or x > lis.back()) {
lis.push_back(x);
best[i] = lis.size();
} else {
int pos = lower_bound(all(lis),x) - lis.begin();
lis[pos] = x;
best[i] = pos + 1;
}
}
//cout << "HELLO";
//for (int i =0;i<n;i++) cout << best[i] << " ";
int rans = best[n-1];
for (int i =n-1;i>=0;i--) {
int p = upper_bound(all(vv),v[i] - X) - vv.begin();
if (p <= n-1) suf = root -> rmq(p,n-1);
else suf = 0;
rans = max(rans, best[i] + suf);
p = lower_bound(all(vv),v[i]) - vv.begin();
if (p <= n-1) suf = root -> rmq(p,n-1);
else suf = 0;
root -> up(p,suf+1);
}
cout << rans;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |