제출 #164146

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
164146		errorgorn	Global Warming (CEOI18_glo)	C++14	100 / 100	367 ms	24568 KiB

glo

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,k;
int arr[200005];
int fw[200005];
int bw[200005];
struct node{
    int s,e,m;
    int val=0;
    node *l,*r;
    node(int _s,int _e){
        s=_s,e=_e,m=(s+e)>>1; //going to lazily build the ST
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void update(int i,int j){
         if (s==e){
            val=j;
         }
         else{
            if (i<=m) l->update(i,j);
            else if (m<i) r->update(i,j);
            val=max(l->val,r->val);
         }
    }
    int query(int i,int j){
        if (i==s && j==e) return val;
        else if (j<=m) return l->query(i,j);
        else if (m<i) return r->query(i,j);
        else return max(l->query(i,m),r->query(m+1,j));
    }
}*root=new node(0,200005);

int main(){
    scanf("%d%d",&n,&k);
    for (int x=0;x<n;x++) scanf("%d",&arr[x]);

    vector<int> v;
    vector<int>::iterator it;
    v.push_back(arr[0]);
    fw[0]=1;
    for (int x=1;x<n;x++){
        if (v.back()<arr[x]){
            v.push_back(arr[x]);
            fw[x]=v.size();
        }
        else{
            it=lower_bound(v.begin(),v.end(),arr[x]);
            v[it-v.begin()]=arr[x];
            fw[x]=it-v.begin()+1;
        }
    }

    v.clear();
    v.push_back(-arr[n-1]);
    bw[n-1]=1;
    for (int x=n-2;x>=0;x--){
        if (v.back()<-arr[x]) {
            v.push_back(-arr[x]);
            bw[x]=v.size();
        }
        else{
            it=lower_bound(v.begin(),v.end(),-arr[x]);
            v[it-v.begin()]=-arr[x];
            bw[x]=it-v.begin()+1;
        }
    }

    //for (int x=0;x<n;x++) printf("%d %d\n",fw[x],bw[x]);

    v.clear();
    for (int x=0;x<n;x++) v.push_back(x);
    sort(v.begin(),v.end(),[](int i,int j){
        return arr[i]>arr[j];
    });

    it=v.begin();

    int ans=-1;
    for (int x=0;x<n;x++){
        while (it!=v.end() && arr[v[x]]<arr[*it]+k) root->update(*it,bw[*it]),it++;
        ans=max(ans,fw[v[x]]+root->query(v[x]+1,n));
    }

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

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

glo.cpp: In function 'int main()':
glo.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
glo.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int x=0;x<n;x++) scanf("%d",&arr[x]);
                           ~~~~~^~~~~~~~~~~~~~

• 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