이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e12;
const int N = 5001;
vi vv;
int idx(int x) {
return upper_bound(all(vv),x)-vv.begin();
}
struct FT{
int n;
vi bit;
FT(int nn) {
n = nn;
bit.assign(nn+1,0);
}
void put(int p,int v) {
for (int i=p;i<=n;i+=i&-i) bit[i]=max(bit[i],v);
}
int get(int p) {
int ans = 0;
for (int i=p;i>0;i-=i&-i) ans=max(ans,bit[i]);
return ans;
}
void reset() {
bit.assign(n+1,0);
}
};
struct ST {
vector<multiset<int,greater<int>>> t;
vector<int> ans;
ST(int nn) {
t.resize(4*nn+1);
ans.resize(4*nn+1);
}
void insert(int node,int l,int r,int p,int v) {
if (l == r) {
t[node].insert(v);
ans[node] = *t[node].begin();
return;
}
int m = (l+r) >> 1;
if (p<=m) insert(2*node,l,m,p,v);
else insert(2*node+1,m+1,r,p,v);
ans[node] = max(ans[2*node],ans[2*node+1]);
}
void erase(int node,int l,int r,int p,int v) {
if (l == r) {
t[node].erase(t[node].find(v));
if (t[node].empty()) ans[node] = 0;
else ans[node] = *t[node].begin();
return;
}
int m = (l+r) >> 1;
if (p<=m) erase(2*node,l,m,p,v);
else erase(2*node+1,m+1,r,p,v);
ans[node] = max(ans[2*node],ans[2*node+1]);
}
int query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return 0;
if (l >= L && r<=R) return ans[node];
int m = (l+r) >> 1;
return max(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R));
}
};
void solve() {
int n,x;
cin >> n >> x;
//corollary: always decrease some prefix
//corollary: if you decrease 1..i you MUST use i.
vi a(n+1);
for (int i=1;i<=n;i++) cin >> a[i];
for (int i=1;i<=n;i++) {
vv.push_back(a[i]);
vv.push_back(a[i]-x);
}
sort(all(vv));
vv.erase(unique(all(vv)),vv.end());
int sz = vv.size();
FT ft(sz);
vi p(n+1),s(n+1);
for (int i=1;i<=n;i++) {
p[i] = ft.get(idx(a[i])-1)+1;
ft.put(idx(a[i]),p[i]);
}
ft.reset();
for (int i=n;i>=1;i--) {
s[i] = ft.get(sz-idx(a[i]))+1;
ft.put(sz-idx(a[i])+1,s[i]);
}
ft.reset();
int ans = 0;
ST st(sz);
for (int i=1;i<=n;i++) st.insert(1,1,sz,idx(a[i]),s[i]);
for (int i=1;i<=n;i++) {
st.erase(1,1,sz,idx(a[i]),s[i]);
ans = max(ans,p[i]+st.query(1,1,sz,idx(a[i]-x)+1,sz));
}
cout << ans << endl;
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Dodi
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |