Submission #63826514

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef set<int> si;
typedef set<long long> sll;

const ll MOD = 998244353;
const ld EPS = 1e-12;

#define endl "\n"
#define sp <<" "<<
#define forn(i, n) for(ll i = 0; i < n; i++)
#define rforn(i, n) for(ll i = n; i >= 0; i--)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 1e18
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())

struct segtree {
    int l, r;
    ll sum;
    unordered_set<int> s;
    segtree *left, *right;

    inline void merge() {
        for (int x : left->s) s.insert(x);
        for (int x : right->s) s.insert(x);
        sum = s.size();
    }

    segtree(int l, int r, vector<int> &data) : l(l), r(r) {
        left = right = nullptr;
        sum = 0;
        if (l == r) {
            sum = 1;
            s.insert(data[l]);
            return;
        }

        int m = (l + r) / 2;
        left = new segtree(l, m, data);
        right = new segtree(m + 1, r, data);
        merge();
    }

    ll query(int ql, int qr) {
        if (ql > r || qr < l) return 0;

        if (ql <= l && r <= qr) return sum;

        return left->query(ql, qr) + right->query(ql, qr);
    }
};

void solution() {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    segtree st(0, n-1, a);

    ll ans = st.query(0, n-1);
    // cerr << ans << endl;
    for (int i = 0; i <= n-1; i++) {
        ans = max(ans, st.query(0, i) + st.query(i+1, n-1));
    }

    cout << ans << endl;
    
    return;
}

signed main() {
    fast_io();

    solution();

    return 0;
}

Submission Info

Judge Result