Submission #1145041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145041		SulA	Global Warming (CEOI18_glo)	C++20	100 / 100	504 ms	56100 KiB

glo

#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;

struct segtree {
    vector<int> tree;
    int offset = 1;
    segtree(int n) {
        while (offset < n) offset <<= 1;
        tree.resize(offset << 1);
    }
    void update(int i, int x) {
        tree[i += offset] = x;
        while (i >>= 1) tree[i] = max(tree[2*i], tree[2*i + 1]);
    }
    int query(int v, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[v];
        if (qr < l || r < ql) return 0;
        int mid = (l+r)/2;
        return max(query(v << 1, l, mid, ql, qr), query(v << 1 | 1, mid+1, r, ql, qr));
    }
    int query(int l, int r) { return query(1, 0, offset - 1, l, r); }
};

int one_bound_fish_very_very_good(vector<int> a, int z) {
    int n = a.size();
    auto b = a;
    for (int i = 0; i < n; i++) {
        b[i] = a[i] + z;
    }
    map<int, vector<int>> comp;
    for (int i = 0; i < n; i++) {
        comp[a[i]].push_back(i);
        comp[b[i]].push_back(i + n);
    }
    int val = 1;
    for (const auto& [x, ind] : comp) {
        for (int i : ind) i < n ? a[i] = val : b[i - n] = val;
        val++;
    }
    int pref[n];
    vector<int> lis;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(lis.begin(), lis.end(), a[i]);
        pref[i] = it - lis.begin() + 1;
        if (it == lis.end()) lis.push_back(a[i]);
        else *it = a[i];
    }
    segtree s(3*n);
    int ans = pref[n-1];
    for (int i = n-1; i >= 0; i--) {
        int mx = s.query(b[i] + 1, 3*n - 1);
        s.update(b[i], mx + 1);
        if (0 < i) ans = max(ans, pref[i-1] + s.query(a[i-1] + 1, 3*n - 1));
    }
    return ans;
}

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

    int n,z; cin>>n>>z;
    vector<int> a(n);
    for (int& x : a) cin>>x;
    int ans = one_bound_fish_very_very_good(a, z);
    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