제출 #482596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
482596		Hazem	Global Warming (CEOI18_glo)	C++14	100 / 100	1256 ms	68064 KiB

glo

#include <bits/stdc++.h>

#define LL long long


using namespace std;

const int N = 2e5+1;
const LL MOD = 1e9+7;

int a[N],dp[N][2],tree[N*4*3],b[N];
int n,k;
map<int,int>mp;
set<int>st;

void update(int v,int tl,int tr,int pos,int val){

    if(tl==tr){
        tree[v] = val;
        return ;
    }

    int mid = (tl+tr)/2;
    if(pos<=mid)update(v*2,tl,mid,pos,val);
    else update(v*2+1,mid+1,tr,pos,val);

    tree[v] = max(tree[v*2],tree[v*2+1]);
}

int get(int v,int tl,int tr,int l,int r){

    if(tl>r||tr<l)
        return 0;

    if(tl>=l&&tr<=r)
        return tree[v];

    int mid = (tl+tr)/2;
    return max(get(v*2,tl,mid,l,r),get(v*2+1,mid+1,tr,l,r));
}

void calc(){

    for(int i=1;i<=n;i++){
        dp[i][0] = get(1,1,3*n,1,b[i]-1)+1;
        if(get(1,1,3*n,b[i],b[i])<dp[i][0])update(1,1,3*n,b[i],dp[i][0]);
    }
    for(int i=1;i<=n;i++)
        update(1,1,3*n,b[i],0);

    for(int i=n;i>=1;i--){
        dp[i][1] = get(1,1,3*n,b[i]+1,3*n)+1;
        if(get(1,1,3*n,b[i],b[i])<dp[i][1])update(1,1,3*n,b[i],dp[i][1]);
    }
    for(int i=1;i<=n;i++)
        update(1,1,3*n,b[i],0);
}

int main(){

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        st.insert(a[i]);
        st.insert(max(0,a[i]-k+1));
        st.insert(min((int)1e9,a[i]+k-1));
    }

    int cnt = 1;
    for(auto x:st)
        mp[x] = cnt++;

    for(int i=1;i<=n;i++)
        b[i] = mp[a[i]];

    calc();
    int ans = 0;
    for(int i=n;i>=1;i--){
        
        ans = max(ans,dp[i][0]+get(1,1,n*3,mp[max(0,a[i]-k+1)],mp[min(a[i]+k-1,(int)1e9)]));
        
        if(get(1,1,3*n,b[i],b[i])<dp[i][1])
            update(1,1,3*n,b[i],dp[i][1]);
    }

    printf("%d\n",ans);
}

컴파일 시 표준 에러 (stderr) 메시지

glo.cpp: In function 'int main()':
glo.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
glo.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25