Submission #959181

#	Time	Username	Problem	Language	Result	Execution time	Memory
959181		Nelt	Global Warming (CEOI18_glo)	C++17	100 / 100	457 ms	30548 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
struct SegTree
{
    ll n;
    vector<pair<ll, ll>> st;
    SegTree(ll sz = 0, bool input = false)
    {
        n = sz;
        st.resize((n + 1) << 1, make_pair(-1, (ll)-1e10));
    }
    void set(ll i, pair<ll, ll> val)
    {
        st[i + n - 1] = val;
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = max(st[i << 1], st[i << 1 | 1]);
    }
    void modify(ll p, pair<ll, ll> val)
    {
        for (st[p += n] = val; p > 1; p >>= 1)
            st[p >> 1] = max(st[p], st[p ^ 1]);
    }
    pair<ll, ll> query(ll l, ll r)
    {
        pair<ll, ll> ans = make_pair(0, -1e10);
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, st[l++]);
            if (r & 1)
                ans = max(ans, st[--r]);
        }
        return ans;
    }
};
void solve()
{
    ll n, x;
    cin >> n >> x;
    ll a[n];
    for (ll &i : a)
        cin >> i;
    ll b[n];
    memcpy(b, a, sizeof(a));
    sort(b, b + n);
    ll dp[n], dp2[n];
    pair<ll, ll> dp1[n];
    SegTree st(n), st1(n);
    for (ll i = 0; i < n; i++)
    {
        dp[i] = st.query(0, lower_bound(b, b + n, a[i]) - b - 1).first + 1;
        st.modify(lower_bound(b, b + n, a[i]) - b, make_pair(dp[i], 0));
    }
    st = SegTree(n);
    for (ll i = 0; i < n; i++)
    {
        pair<ll, ll> tmp = st.query(0, lower_bound(b, b + n, a[i] + x) - b - 1), tmp1 = st1.query(0, lower_bound(b, b + n, a[i]) - b - 1);
        dp1[i] = max(make_pair(tmp1.first + 1, tmp1.second), make_pair(tmp.first + 1, min(x, max(-x, tmp.second - a[i] + 1))));
        st.modify(lower_bound(b, b + n, a[i]) - b, make_pair(dp[i], a[i]));
        st1.modify(lower_bound(b, b + n, a[i]) - b, dp1[i]);
    }
    st = SegTree(n);
    st1 = SegTree(n);
    ll c[n];
    for (ll i = 0; i < n; i++)
        c[i] = a[i] + dp1[i].second;
    sort(c, c + n);
    for (ll i = 0; i < n; i++)
    {
        pair<ll, ll> tmp = st.query(0, lower_bound(c, c + n, a[i]) - c - 1);
        dp2[i] = tmp.first + 1;
        dp2[i] = max(dp2[i], st.query(0, lower_bound(b, b + n, a[i]) - b - 1).first + 1);
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++)
        ans = max({ans, dp[i], dp2[i], dp1[i].first});
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll i = 1; i <= t; i++)
        solve();
    cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\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