제출 #857332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
857332		vjudge1	Global Warming (CEOI18_glo)	C++17	0 / 100	83 ms	4948 KiB

glo

//ulimit -s unlimited
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<long long>
#define vi vector<int>
#define vb vector<bool>
#define pql priority_queue<long long>
#define pqp priority_queue<pair<ll,ll> >
#define pqs priority_queue<ll,vl,greater<ll> >
#define md ((ll) 1e9+7)

vl lis(vl a,ll n){

    vl ans(n);
    ll i,j,k,m;
    vl ln;
    for(i=0;i<n;i++){
        j = lower_bound(ln.begin(),ln.end(),a[i])-ln.begin();
        if(j==ln.size()){
            ln.push_back(a[i]);
            ans[i] = j+1;
        }
        else{
            if(ln[j]>a[i]){
                ln[j] = a[i];
                ans[i] = j+1;
            }
            else{
                ans[i] = j+1;
            }
        }
    }
    return ans;

}

void solve(){

    ll i,j,k,n,m;
    ll x;
    cin>>n>>x;
    vl a(n);
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    vl fl = lis(a,n);
    ll ans = 0;
    for(auto c:fl){
        ans = max(c,ans);
    }
    for(i=0;i<n;i++){
        a[i] =  -a[i];
    }

    vl bl;
    for(i=n-1;i>=0;i--){
        //a[i];
        j = lower_bound(bl.begin(),bl.end(),-(a[i]-x))-bl.begin();
        ans = max(ans,fl[i]+j);
        j = lower_bound(bl.begin(),bl.end(),-a[i]) - bl.begin();
        if(j == bl.size()){
            bl.push_back(-a[i]);
        }
        else{
            if(bl[j]>-a[i]){
                bl[j] = -a[i];
            }
        }
    }
    cout<<ans<<endl;


}

int main(){
    //ios::sync_with_stdio(0);
    //cin.tie(0);cout.tie(0);
    int t;
    //cin >> t;
    t = 1;
    while(t--)
        solve();
    return 0;
}
/*
8 10
7 3 5 12 2 7 3 4
*/

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

glo.cpp: In function 'std::vector<long long int> lis(std::vector<long long int>, long long int)':
glo.cpp:20:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(j==ln.size()){
      |            ~^~~~~~~~~~~
glo.cpp:16:12: warning: unused variable 'k' [-Wunused-variable]
   16 |     ll i,j,k,m;
      |            ^
glo.cpp:16:14: warning: unused variable 'm' [-Wunused-variable]
   16 |     ll i,j,k,m;
      |              ^
glo.cpp: In function 'void solve()':
glo.cpp:62:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         if(j == bl.size()){
      |            ~~^~~~~~~~~~~~
glo.cpp:40:12: warning: unused variable 'k' [-Wunused-variable]
   40 |     ll i,j,k,n,m;
      |            ^
glo.cpp:40:16: warning: unused variable 'm' [-Wunused-variable]
   40 |     ll i,j,k,n,m;
      |                ^

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