Submission #644798

#	Time	Username	Problem	Language	Result	Execution time	Memory
644798		Karuk	Global Warming (CEOI18_glo)	C++14	100 / 100	138 ms	20428 KiB

glo

#include<bits/stdc++.h>
using namespace std;
long long max(long long &a,long long &b) {return a>b?a:b;}
int main() {
    long long n,x;cin>>n>>x;
    long long a[n];
    long long poslis[n];
    vector<long long>lis(n,1e18);
    vector<vector<long long> >history(n,{(long long)(1e18)});
    long long ans=0;
    for(int i=0;i<n;i++) {
        long long y;cin>>y;
        long long pos=lower_bound(lis.begin(),lis.end(),y)-lis.begin();
        history[pos].push_back(y);
        poslis[i]=pos;
        lis[pos]=y;
        ans=max(ans,pos+1);
    }
    vector<long long>revlis(n,1e18);
    for(int i=n-1;i>0;i--) {
        long long cur=history[poslis[i]].back();
        history[poslis[i]].pop_back();
        lis[poslis[i]]=history[poslis[i]].back();
        cur+=x;
        cur=-cur;
        long long pos=lower_bound(revlis.begin(),revlis.end(),cur)-revlis.begin();
        revlis[pos]=cur;
        cur=-cur;
        long long pos1=lower_bound(lis.begin(),lis.end(),cur)-lis.begin();
        ans=max(ans,pos1+pos+1);
    }
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:6:15: warning: unused variable 'a' [-Wunused-variable]
    6 |     long long a[n];
      |               ^

• 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