Submission #954689

#	Time	Username	Problem	Language	Result	Execution time	Memory
954689		0x34c	Global Warming (CEOI18_glo)	C++17	100 / 100	550 ms	47532 KiB

glo

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll

using namespace std;

class SegTree {
private:
    vector<int> tree;
    int n;

    int _query(int l, int r, int v, int tl, int tr) {
        if(tr < l || r < tl)
            return 0;
        if(l <= tl && tr <= r)
            return tree[v];
        
        int m = (tl + tr) / 2;
        return max(_query(l, r, 2*v, tl, m), _query(l, r, 2*v + 1, m + 1, tr));
    }

    void _update(int idx, int val, int v, int tl, int tr) {
        if(tl == tr)
            tree[v] = val;
        else {
            int m = (tl + tr) / 2;
            if(idx <= m) _update(idx, val, 2*v, tl, m);
            else _update(idx, val, 2*v + 1, m + 1, tr);
            tree[v] = max(tree[2*v], tree[2*v + 1]);
        }
    }
public:
    SegTree(int N) {
        n = N;
        tree.resize(4*n, 0);
    }
    int query(int l, int r) {
        if(l > r) return 0;
        return _query(l, r, 1, 0, n - 1);
    }
    void update(int idx, int val) {
        return _update(idx, val, 1, 0, n - 1);
    }
};


signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int N, X;
    cin >> N >> X;

    vector<int> arr(N);
    map<int, int> cmp;
    set<int> vals;
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
        vals.insert(arr[i]);
    }

    int cmpi = 0;
    for(int i : vals)
        cmp[i] = cmpi++;
    
    // we do the longest decreasing sequence
    SegTree tree(cmpi);
    vector<vector<pii>> sols(cmpi);
    vector<pii> upd(N, {-1, -1});
    for(int i = N - 1; i >= 0; i--) {
        int nxt = cmp[arr[i]] + 1;
        int sol = 1 + tree.query(nxt, cmpi - 1);
        if(sols[nxt - 1].empty() || sols[nxt - 1].back().first < sol) {
            upd[i] = {nxt - 1, sols[nxt - 1].empty() ? 0 : sols[nxt - 1].back().first};
            sols[nxt - 1].push_back({sol, i});
            tree.update(nxt - 1, sol);
        }
    }

    // for(int i = 0; i < cmpi; i++)
    //     cout << tree.query(i, i) << ' ';
    // cout << endl;

    // for(int i = 0; i < N; i++)
    //     cout << "(" << upd[i].first << ", " << upd[i].second << ") ";
    // cout << endl;

    // now we find sol for everything
    vector<int> lis;
    int res = 0;
    for(int i = 0; i < N; i++) {
        if(upd[i].first != -1) {
            tree.update(upd[i].first, upd[i].second);
        }

        // for(int i = 0; i < cmpi; i++)
        //     cout << tree.query(i, i) << ' ';
        // cout << endl;

        int it = arr[i] - X;
        int idx = 0;
        if(lis.empty() || lis.back() < it) {
            lis.push_back(it);
            idx = lis.size() - 1;
        }
        else {
            int l = 0, r = lis.size() - 1;
            int lb = -1;
            while(l <= r) {
                int m = l + (r - l) / 2;
                if(lis[m] >= it) {
                    lb = m;
                    r = m - 1;
                }
                else l = m + 1;
            }

            lis[lb] = it;
            idx = lb;
        }

        // now we find LIS
        auto iter = cmp.upper_bound(it);
        if(iter == cmp.end())
            res = max(res, idx + 1);
        else
            res = max(res, idx + 1 + tree.query(iter->second, cmpi - 1));
    }

    cout << res << endl;
}

• 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