#include <bits/stdc++.h>
#define el '\n'
#define FNAME "IMPARR"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9+7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
int n,D;
vector<int> a;
void init(){
cin>>n>>D;
vector<int> org(n);
for (int &x:org) cin>>x;
vector<int> compress(allof(org));
sort(allof(compress));
compress.resize(unique(allof(compress))-compress.begin());
a.resize(n+1,-1);
for (int i=1;i<=n;i++){
int t = lower_bound(allof(compress),org[i-1]) - compress.begin() + 1;
a[i] = t;
}
}
namespace Bitmask2N{
bool isStrictlySorted(const vector<int> &a){
for (int i=1;i<(int)a.size();i++){
if (a[i-1] >= a[i]) return false;
}
return true;
}
void solve(){
int res = 0;
for (int mask = 0; mask < (1 << n); mask++) {
vector<int> indices, val;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) indices.push_back(i);
}
bool ok = true;
for (int i = 1; i < (int)indices.size(); i++) {
if (abs(indices[i] - indices[i - 1]) > D) {
ok = false;
break;
}
}
if (!ok) continue;
for (int idx : indices) val.push_back(a[idx + 1]);
if (isStrictlySorted(val)) maximize(res, indices.size());
}
cout << res;
exit(0);
}
};
namespace SolutionNN{
void solve(){
// ! dp[i]: Longest Increasing Subsequence collect and end at the element at index i
vector<int> dp(n+1,1);
dp[0]=0;
for (int i=1;i<=n;i++){
for (int j=i-1;j>=max(0,i-D);j--){
if (a[i] > a[j]) maximize(dp[i],dp[j]+1);
}
}
cout<< *max_element(allof(dp));
exit(0);
}
};
namespace SubtaskD1{
void solve(){
// ! dp[i]: Longest Increasing Subsequence collect and end at the element at index i
vector<int> dp(n+1,1);
dp[0]=0;
for (int i=1;i<=n;i++){
if (a[i] > a[i-1]) maximize(dp[i],dp[i-1]+1);
}
cout<< *max_element(allof(dp));
exit(0);
}
};
namespace NormalLIS{
void solve(){
vector<int> dp;
vector<int> fordp(allof1(a));
for (int x:fordp){
vector<int>::iterator it = lower_bound(allof(dp),x);
if (it == dp.end()) dp.push_back(x);
else *it = x;
}
cout<<dp.size();
exit(0);
}
};
namespace Finale{
struct SegmentTree{
int n;
vector<int> st;
vector<multiset<int>> leaf;
SegmentTree(int N=0){
n=N;
if (n>0){
st.assign(4*n+1,0);
leaf.resize(n+1);
}
}
void update(int node,int l,int r,int pos){
if (l==r){
st[node] = (leaf[pos].empty() ? 0 : *leaf[pos].rbegin());
return;
}
int mid = (l+r)>>1;
if (pos<=mid) update(2*node,l,mid,pos);
else update(2*node+1,mid+1,r,pos);
st[node] = max(st[2*node],st[2*node+1]);
}
void update(int pos){
update(1,1,n,pos);
}
void insert(int pos,int val){
leaf[pos].insert(val);
update(pos);
}
void erase(int pos,int val){
multiset<int>::iterator it = leaf[pos].find(val);
if (it != leaf[pos].end()) leaf[pos].erase(it);
update(pos);
}
int getMax(int node,int l,int r,int wanted_l,int wanted_r){
if (wanted_r<l or r<wanted_l) return 0;
if (wanted_l<=l and r<=wanted_r) return st[node];
int mid = (l+r)>>1;
return max(getMax(2*node,l,mid,wanted_l,wanted_r),
getMax(2*node+1,mid+1,r,wanted_l,wanted_r));
}
int getMax(int l,int r){
if (l>r) return 0;
return getMax(1,1,n,l,r);
}
};
void solve(){
SegmentTree st(n);
vector<int> dp(n+1,0);
for (int i=1;i<=n;i++){
dp[i] = st.getMax(1,a[i]-1) + 1;
st.insert(a[i],dp[i]);
if (i>=D){
st.erase(a[i-D],dp[i-D]);
}
}
cout<<*max_element(allof(dp));
exit(0);
}
}
void sol(){
if (n<=20) Bitmask2N::solve();
if (n<=7000) SolutionNN::solve();
if (D==1) SubtaskD1::solve();
if (D==n) NormalLIS::solve();
Finale::solve();
}
int main(){
setup();
init();
sol();
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'void setup()':
Main.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
16 | freopen(FNAME".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen(FNAME".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... |