Submission #1215770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215770		giorgi123glm	Global Warming (CEOI18_glo)	C++20	100 / 100	365 ms	23324 KiB

glo

#include <iostream>
#include <functional>
#include <set>
#include <map>
#include <array>
#include <algorithm>
#include <numeric>
using namespace std;

#define int long long

template <typename T>
class segment_tree {
    public:
        int siz = 1;
        vector <T> segtree;
        function <T(T, T)> merge;
        
        segment_tree(function <T(T, T)> IN) : merge (IN) {}

        void resize (int n) {
            while (siz < n)
                siz *= 2;
            segtree.resize (2 * siz);
        }

        void update (int ind, T K) {
            int u = siz + ind - 1;
            segtree[u] = K;
            u /= 2;
            while (u)
                segtree[u] = merge (
                    segtree[2 * u], segtree[2 * u + 1]
                ), u /= 2;
        }

        T get (int L, int R, int u, int l, int r) {
            if (r < L || R < l)
                return T();

            if (L <= l && r <= R)
                return segtree[u];

            const int m = (l + r) / 2;
            return merge (
                get (L, R, 2 * u, l, m),
                get (L, R, 2 * u + 1, m + 1, r)
            );
        }

        T get (int L, int R) {
            return get (L, R, 1, 1, siz);
        }
};

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0, X = 0;
    cin >> N >> X;

    vector <int> v (N + 1);
    for (int i = 1; i <= N; i++)
        cin >> v[i];

    vector <pair <int, int> > comp;
    comp.reserve (N + 1);
    vector <int> revcomp (N + 1);
    {
        // comp
        map <int, int> m;
        for (int i = 1; i <= N; i++)
            m[v[i]] = 1;

        int free = 1;
        for (pair <const int, int>& e : m)
            e.second = free++;

        for (int i = 1; i <= N; i++) {
            comp.emplace_back (v[i], m[v[i]]);
            revcomp[m[v[i]]] = v[i];
            v[i] = m[v[i]];
        }
    }
    sort (comp.begin(), comp.end());
    comp.emplace_back (1e18, 1e18);

    // for (int i = 1; i <= N; i++)
    //     cout << v[i] << ' ';
    // cout << '\n';
    // for (pair <int, int>& e : comp)
    //     cout << e.first << ' ' << e.second << '\n';

    //          cnt num
    vector <pair <int, int> > preflis (N + 1);
    {
        segment_tree <int> segtree (
            [](int a, int b) {
                return max (a, b);
            }
        );
        segtree.resize (N + 1);
        for (int i = 1; i <= N; i++) {
            int maxcnt = segtree.get (1, v[i] - 1) + 1;

            preflis[i] = {maxcnt, v[i]};
            segtree.update (v[i], maxcnt);
        }

        for (int i = 1; i <= N; i++) {
            if (preflis[i].first == preflis[i - 1].first) {
                if (preflis[i].second > preflis[i - 1].second)
                    preflis[i] = preflis[i - 1];
            } else if (preflis[i] > preflis[i - 1]){
                preflis[i] = max (preflis[i], preflis[i - 1]);
            }
        }
    }

    segment_tree <int> revlis (
        [](int a, int b) {
            return max (a, b);
        }
    );
    revlis.resize (N + 1);

    int ans = preflis[N].first;
    for (int i = N; i >= 1; i--) {
        int maxcnt = revlis.get (v[i] + 1, revlis.siz) + 1;
        revlis.update (v[i], maxcnt);

        int target = revcomp[preflis[i - 1].second] - X + 1;
        int lower = (*lower_bound (comp.begin(), comp.end(), (pair <int, int>){target, -1e18})).second;
        ans = max (
            ans,
            preflis[i - 1].first + revlis.get (lower, revlis.siz)
        );
    }

    cout << ans << '\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