oj.uz

Submission #900068

# Submission time Handle Problem Language Result Execution time Memory
900068 2024-01-07T14:44:07 Z vgtcross Sequence (APIO23_sequence) C++17
0 / 100
 2000 ms 130720 KB 
#include <bits/stdc++.h>

#define MODE 0

#if MODE
#define debug(x) cout << #x << ": " << (x) << endl
#define log(x) cout << (x) << endl
#define test(x) x
#else
#define debug(x)
#define log(x)
#define test(x)
#endif

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
#define X real()
#define Y imag()

using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using P = complex<ll>;

template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}

const ll M = 1000000007; // 998244353

struct segtree {
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    int v = 1e9;
    
    segtree(int L, int R) : l(L), r(R) {
        m = (l + r) / 2;
        if (l == r) return;
        lc = new segtree(l, m);
        rc = new segtree(m+1, r);
    }
    
    void point_set(int i, int u) {
        if (l == i && i == r) {
            chmin(v, u);
            return;
        }
        if (i <= m) lc->point_set(i, u);
        else rc->point_set(i, u);
        v = min(lc->v, rc->v);
    }
    
    int range_min(int L, int R) {
        if (L > R) return 1e9;
        if (l == L && r == R) return v;
        return min(lc->range_min(L, min(R, m)), rc->range_min(max(m+1, L), R));
    }
    
    void clear() {
        for (auto u : {lc, rc}) if (u != nullptr) {
            u->clear();
            delete u;
        }
    }
};

struct segtree_pref {
    int l, r, m;
    segtree_pref *lc = nullptr, *rc = nullptr;
    int p = 1, minp = 0, maxp = 1;
    
    segtree_pref(int L, int R) : l(L), r(R) {
        m = (l + r) / 2;
        if (l == r) return;
        lc = new segtree_pref(l, m);
        rc = new segtree_pref(m+1, r);
        p = lc->p + rc->p;
        minp = min(lc->minp, lc->p + rc->minp);
        maxp = max(lc->maxp, lc->p + rc->maxp);
    }
    
    void point_set(int i, int u) {
        if (l == i && i == r) {
            p = u;
            minp = min(0, u);
            maxp = max(0, u);
            return;
        }
        if (i <= m) lc->point_set(i, u);
        else rc->point_set(i, u);
        p = lc->p + rc->p;
        minp = min(lc->minp, lc->p + rc->minp);
        maxp = max(lc->maxp, lc->p + rc->maxp);
    }
    
    int pref_sum(int i) {
        if (i < 0) return 0;
        if (l == i && i == r) return p;
        if (i <= m) return lc->pref_sum(i);
        else return lc->p + rc->pref_sum(i);
    }
    
    array<int, 3> range_query(int L, int R) {
        if (L > R) return {0, 0, 0};
        if (l == L && r == R) return {p, minp, maxp};
        auto a = lc->range_query(L, min(R, m));
        auto b = rc->range_query(max(m+1, L), R);
        return {a[0] + b[0], min(a[1], a[0] + b[1]), max(a[2], a[0] + b[2])};
    }
    
    void clear() {
        for (auto u : {lc, rc}) if (u != nullptr) {
            u->clear();
            delete u;
        }
    }
};

int compress(vector<int> &v, int w = 0) {
    int n = v.size();
    vector<pii> u(n);
    for (int i = 0; i < n; ++i) u[i] = {v[i], i};
    sort(all(u));
    for (int i = 0; i < n; ++i) {
        if (i > 0) w += u[i].fi != u[i-1].fi;
        v[u[i].se] = w;
    }
    return w;
}

const int N = 500500;
vector<int> idx[N];

int sequence(int n, vector<int> v) {
    for (int i = 0; i < n; ++i) idx[v[i]].push_back(i);
    segtree_pref segp(0, n-1);
    int ans = 0;
    for (int a = 1; a <= n; ++a) {
        for (int i : idx[a-1]) segp.point_set(i, -1);
        for (int i : idx[a]) segp.point_set(i, 0);
        idx[a].push_back(n);
        vector<pii> u;
        int b = 0;
        for (int i : idx[a]) {
            int p = segp.pref_sum(b);
            auto c = segp.range_query(b+1, i-1);
            u.push_back({p + c[1], p + c[2]});
            b = i;
        }
        idx[a].pop_back();
        int m = u.size();
        {
            set<int> st;
            vector<pii> ev;
            for (int i = 0; i < m; ++i) {
                ev.push_back({u[i].fi, i});
                ev.push_back({u[i].se+1, i});
            }
            sort(all(ev));
            for (int i = 0; i < ev.size(); ++i) {
                int j = i;
                while (j < ev.size() && ev[i].fi == ev[j].fi) {
                    if (st.count(ev[j].se)) st.erase(ev[j++].se);
                    else st.insert(ev[j++].se);
                }
                if (st.size()) chmax(ans, *st.rbegin() - *st.begin());
            }
        }
        {
            vector<int> vals(2*m);
            for (int i = 0; i < m; ++i) {
                vals[i] = u[i].fi - i;
                vals[i+m] = u[i].se - i;
            }
            compress(vals);
            int w = compress(vals);
            vector<array<int, 3>> ev;
            for (int i = 0; i < m; ++i) {
                ev.push_back({2 * u[i].se, vals[i+m], i});
                ev.push_back({2 * u[i].fi - 1, vals[i], i});
            }
            sort(all(ev));
            segtree seg(0, w);
            for (auto c : ev) {
                if (c[0] & 1) chmax(ans, c[2] - seg.range_min(c[1], w));
                else seg.point_set(c[1], c[2]);
            }
            seg.clear();
        }
        {
            vector<int> vals(2*m);
            for (int i = 0; i < m; ++i) {
                vals[i] = u[i].fi + i;
                vals[i+m] = u[i].se + i;
            }
            int w = compress(vals);
            vector<array<int, 3>> ev;
            for (int i = 0; i < m; ++i) {
                ev.push_back({2 * u[i].se + 1, vals[i+m], i});
                ev.push_back({2 * u[i].fi, vals[i], i});
            }
            sort(rall(ev));
            segtree seg(0, w);
            for (auto c : ev) {
                if (c[0] & 1) chmax(ans, c[2] - seg.range_min(c[1], w));
                else seg.point_set(c[1], c[2]);
            }
            seg.clear();
        }
    }
    segp.clear();
    return ans;
}

#if MODE
int main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int n;
    cin >> n;
    
    vector<int> v(n);
    for (int &i : v) cin >> i;
    cout << sequence(n, v) << '\n';
    
    return 0;
}
#endif

Compilation message

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:165:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for (int i = 0; i < ev.size(); ++i) {
      |                             ~~^~~~~~~~~~~
sequence.cpp:167:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |                 while (j < ev.size() && ev[i].fi == ev[j].fi) {
      |                        ~~^~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Incorrect 4 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Incorrect 4 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 1041 ms 98088 KB Output is correct
3 Correct 1046 ms 97740 KB Output is correct
4 Execution timed out 2009 ms 87068 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 1678 ms 130720 KB Output is correct
3 Execution timed out 2025 ms 114276 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1253 ms 97684 KB Output is correct
2 Correct 1329 ms 97672 KB Output is correct
3 Correct 1211 ms 97584 KB Output is correct
4 Correct 1272 ms 97872 KB Output is correct
5 Incorrect 1124 ms 97448 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Incorrect 4 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12124 KB Output is correct
2 Correct 3 ms 12124 KB Output is correct
3 Correct 3 ms 12124 KB Output is correct
4 Incorrect 4 ms 12124 KB Output isn't correct
5 Halted 0 ms 0 KB -