Submission #900078

#TimeUsernameProblemLanguageResultExecution timeMemory
900078vgtcrossSequence (APIO23_sequence)C++17
100 / 100
1502 ms165708 KiB
#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 = -1; 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();) { 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()); i = j; } } { 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(0, c[1])); 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 (stderr)

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();) {
      |                             ~~^~~~~~~~~~~
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) {
      |                        ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...