Submission #866515

#	Time	Username	Problem	Language	Result	Execution time	Memory
866515		12345678	Global Warming (CEOI18_glo)	C++17	100 / 100	145 ms	8788 KiB

glo

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;
int n, d, dp[nx], dp2[nx], ans, cnt;
map<int, int> mp;

struct segtree
{
    int d[4*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) 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>>d;
    vector<int> v(n), vs(n), t;
    for (int i=0; i<n; i++) cin>>v[i], vs[i]=v[i];
    sort(vs.begin(), vs.end());
    for (int i=n-1; i>=0; i--)
    {
        auto itr=lower_bound(t.begin(), t.end(), -v[i]);
        dp[i]=itr-t.begin()+1;
        if (itr==t.end()) t.push_back(-v[i]);
        else *itr=-v[i];
    }
    t.clear();
    for (int i=0; i<n; i++)
    {
        auto itr=lower_bound(t.begin(), t.end(), v[i]);
        dp2[i]=itr-t.begin()+1;
        if (itr==t.end()) t.push_back(v[i]);
        else *itr=v[i];
    }
    for (int i=n-1; i>=0; i--)
    {
        //cout<<v[i]<<' '<<upper_bound(vs.begin(), vs.end(), v[i]-d)-vs.begin()+1<<' '<<lower_bound(vs.begin(), vs.end(), v[i])-vs.begin()+1<<'\n';
        //cout<<"here"<<' '<<dp2[i]<<' '<<s.query(1, n, 1, upper_bound(vs.begin(), vs.end(), v[i]-d)-vs.begin()+1, n)<<'\n';
        ans=max(ans, dp2[i]+s.query(1, n, 1, upper_bound(vs.begin(), vs.end(), v[i]-d)-vs.begin()+1, n));
        s.update(1, n, 1, lower_bound(vs.begin(), vs.end(), v[i])-vs.begin()+1, dp[i]);
    }
    cout<<ans;
}

• 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