This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define int ll
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 2e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
int dp[MAXN][3],a[MAXN];
int n,k;
struct fenwick_tree{
vi f;
int _n;
void update(int id, int val){
for(; id<=_n; id += id&-id){
maxi(f[id],val);
}
}
int get(int id){
int res = 0;
for(; id>0; id-=id&-id){
maxi(res,f[id]);
}
return res;
}
fenwick_tree(int _n1):_n(_n1){
f.assign(_n,0);
}
};
void sub4(){
vi cur;
REP(i,1,n) cur.push_back(a[i]);
cur.push_back(0);
sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin());
fenwick_tree fen(n+3);
REP(i,1,n){
a[i] = lower_bound(ALL(cur),a[i])-cur.begin()+1;
int val = fen.get(a[i]-1);
fen.update(a[i],val+1);
}
cout << fen.get(n);
}
void sub3(){
int res = 0;
REP(i,1,n){
REP(j,1,i-1){
if(a[i]>a[j]) maxi(dp[i][0],dp[j][0]);
if(a[i]>a[j] || abs(a[i]-a[j])<k){
maxi(dp[i][1],dp[j][0]);
}
if(a[i]>a[j]) maxi(dp[i][2],max(dp[j][0],max(dp[j][1],dp[j][2])));
}
++dp[i][0];
++dp[i][1];
++dp[i][2];
maxi(res,max(dp[i][0],max(dp[i][1],dp[i][2])));
}
cout << res;
}
void sub7(){
vi cur;
REP(i,1,n){
cur.push_back(a[i]);
cur.push_back(a[i]+k);
}
cur.push_back(-1);
sort(ALL(cur)); cur.resize(unique(ALL(cur))-cur.begin());
fenwick_tree fen1(n*3+3),fen2(n*3+3),fen3(n*3+3);
REP(i,1,n){
int tmp = lower_bound(ALL(cur),a[i]+k)-cur.begin()+1;
int ai = lower_bound(ALL(cur),a[i])-cur.begin()+1;
dp[i][0] = fen1.get(ai-1);
dp[i][1] = fen1.get(tmp-1);
dp[i][2] = max(dp[i][0],max(fen2.get(ai-1),fen3.get(a[i]-1)));
fen1.update(ai,dp[i][0]+1);
fen2.update(ai,dp[i][1]+1);
fen3.update(ai,dp[i][2]+1);
}
int m = n*3;
cout << max(fen1.get(m),max(fen2.get(m),fen3.get(m)));
}
void sube(){
vi dp1,dp2;
dp1.push_back(-1e18);
dp2.push_back(-1e18);
REP(i,1,n){
int lg = lower_bound(dp1.begin(),dp1.end(),a[i])-dp1.begin();
if(lg==SZ(dp1)) dp1.push_back(a[i]); else dp1[lg] = a[i];
int tmp = lg;
lg = lower_bound(dp2.begin(),dp2.end(),a[i])-dp2.begin();
if(lg==SZ(dp2)) dp2.push_back(a[i]); else dp2[lg] = a[i];
if(SZ(dp2)<=tmp) dp2.push_back(1e18);
mini(dp2[tmp],a[i]-k);
}
cout << SZ(dp2)-1;
}
void solve(){
cin >> n >> k;
REP(i,1,n){
cin >> a[i];
}
if(k==0){
sub4(); return ;
}
// sub3();
sube();
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message (stderr)
glo.cpp: In function 'int main()':
glo.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
159 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
glo.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
160 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |