제출 #1358575

#제출 시각아이디문제언어결과실행 시간메모리
135857512345678Global Warming (CEOI18_glo)C++17
100 / 100
315 ms26464 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, x, a[nx], b[nx], lis[nx], lds[nx], res, t; // lis[i] = lis when considering prefix i
map<int, int> mp;

struct segtree
{
    int d[8*nx];
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (qr<l||r<ql||qr<ql) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>x;
    for (int i=1; i<=n; i++) cin>>a[i], b[i]=-a[i], mp[a[i]]=mp[a[i]+x]=0;
    for (auto &[_, y]:mp) y=++t;
    vector<int> v;
    for (int i=1; i<=n; i++)
    {
        auto idx=lower_bound(v.begin(), v.end(), a[i])-v.begin();
        if (idx==v.size()) v.push_back(a[i]);
        else v[idx]=a[i];
        lis[i]=idx+1;
    }   
    v.clear();
    for (int i=n; i>=1; i--)
    {
        auto idx=lower_bound(v.begin(), v.end(), b[i])-v.begin();
        if (idx==v.size()) v.push_back(b[i]);
        else v[idx]=b[i];
        lds[i]=idx+1;
    }
    for (int i=1; i<=n; i++) res=max({res, lis[i], lds[i]});
    for (int i=1; i<=n; i++)
    {
        res=max(res, s.query(1, t, 1, 1, mp[a[i]+x]-1)+lds[i]);
        s.update(1, t, 1, mp[a[i]], lis[i]);
    }
    cout<<res;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…