Submission #754985

#TimeUsernameProblemLanguageResultExecution timeMemory
754985ZaniteSequence (APIO23_sequence)C++17
100 / 100
1834 ms100180 KiB
#include "sequence.h" // 赤コーダーになりたい // お願い いいですか? #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> // Pragmas // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // Namespaces using namespace std; using namespace __gnu_pbds; // Data types using si = short int; using ll = long long; using lll = __int128; using ld = long double; // Pairs using pii = pair<int, int>; using psi = pair<si, si>; using pll = pair<ll, ll>; using plll = pair<lll, lll>; using pld = pair<ld, ld>; #define fi first #define se second // For #define Frue(i, n, N) for (int i = (n); i <= (N); i++) #define Fru(i, n, N) for (int i = (n); i < (N); i++) #define Frde(i, n, N) for (int i = (n); i >= (N); i--) #define Frd(i, n, N) for (int i = (n); i > (N); i--) // PBDS template<typename Z> using ordered_set = tree<Z, null_type, less<Z>, rb_tree_tag, tree_order_statistics_node_update>; // Various outputs template<typename Y, typename Z> ostream& operator<<(ostream &os, const pair<Y, Z> &p) { return os << '(' << p.fi << ',' << p.se << ')'; } template<typename Z> ostream& operator<<(ostream &os, const vector<Z> &v) { os << '{'; bool _first = 1; for (auto &i : v) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } template<typename Z, unsigned long long sz> ostream& operator<<(ostream &os, const array<Z, sz> &arr) { os << '{'; bool _first = 1; for (auto &i : arr) {if (!_first) os << ", "; os << i; _first = 0;} return os << '}'; } // Quick macro functions #define sqr(x) ((x)*(x)) #define debug(x) cout << #x << " = " << (x) << '\n' #define debugV(v, x) cout << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define rrebug(x) cerr << #x << " = " << (x) << '\n' #define rrebugV(v, x) cerr << #v << "[" << (x) << "] = " << (v[x]) << '\n' #define All(x) x.begin(), x.end() #define Sort(x) sort(All(x)) #define Reverse(x) reverse(All(x)) #define Uniqueify(x) Sort(x); x.erase(unique(All(x)), x.end()) #define RandomSeed chrono::steady_clock::now().time_since_epoch().count() #define MultipleTestcases int _tc; cin >> _tc; for (int _cur_tc = 1; _cur_tc <= _tc; _cur_tc++) // Check min and max template<typename Z> void chmin(Z &a, Z b) {a = min(a, b);} template<typename Z> void chmax(Z &a, Z b) {a = max(a, b);} // Modular arithmetic template<int MOD> class ModInt { public: int v; ModInt() : v(0) {} ModInt(long long _v) { v = int((-MOD < _v && _v < MOD) ? (_v) : (_v % MOD)); if (v < 0) v += MOD; } friend bool operator==(const ModInt &a, const ModInt &b) {return a.v == b.v;} friend bool operator!=(const ModInt &a, const ModInt &b) {return a.v != b.v;} friend bool operator< (const ModInt &a, const ModInt &b) {return a.v < b.v;} friend bool operator<=(const ModInt &a, const ModInt &b) {return a.v <= b.v;} friend bool operator> (const ModInt &a, const ModInt &b) {return a.v > b.v;} friend bool operator>=(const ModInt &a, const ModInt &b) {return a.v >= b.v;} ModInt &operator+=(const ModInt &a) {if ((v += a.v) >= MOD) v -= MOD; return *this;} ModInt &operator-=(const ModInt &a) {if ((v -= a.v) < 0) v += MOD; return *this;} ModInt &operator*=(const ModInt &a) {v = 1ll * v * a.v % MOD; return *this;} ModInt &operator/=(const ModInt &a) {return (*this) *= inverse(a);} friend ModInt pow(ModInt a, long long x) { ModInt res = 1; for (; x; x /= 2, a *= a) if (x & 1) res *= a; return res; } friend ModInt inverse(ModInt a) {return pow(a, MOD - 2);} ModInt operator+ () const {return ModInt( v);} ModInt operator- () const {return ModInt(-v);} ModInt operator++() const {return *this += 1;} ModInt operator--() const {return *this -= 1;} friend ModInt operator+(ModInt a, const ModInt &b) {return a += b;} friend ModInt operator-(ModInt a, const ModInt &b) {return a -= b;} friend ModInt operator*(ModInt a, const ModInt &b) {return a *= b;} friend ModInt operator/(ModInt a, const ModInt &b) {return a /= b;} friend istream &operator>>(istream &is, ModInt &v) {return is >> v.v;} friend ostream &operator<<(ostream &os, const ModInt &v) {return os << v.v;} }; const int ModA = 998244353; const int ModC = 1e9 + 7; using MintA = ModInt<ModA>; using MintC = ModInt<ModC>; // Other constants const ll INF = 1e18; const ll iINF = 1e9; const ld EPS = 1e-9; const ld iEPS = 1e-6; struct SegtreeLazy { using Elm = int; Elm DEFAULT = -iINF; #define m ((l+r) >> 1) #define lc (pos << 1) #define rc (lc | 1) int sz; vector<Elm> seg, lazy; SegtreeLazy(int sz = 1) : sz(sz) { seg = vector<Elm>((sz << 2) + 1, DEFAULT); lazy = vector<Elm>((sz << 2) + 1, 0); } #define updateNode(pos, val) seg[pos] += val, lazy[pos] += val #define merge(a, b) max(a, b) void checkLazy(int pos, int l, int r) { if (lazy[pos]) { updateNode(lc, lazy[pos]); updateNode(rc, lazy[pos]); lazy[pos] = 0; } } void build(int pos, int l, int r, vector<Elm> &v) { if (l == r) { seg[pos] = v[l]; return; } build(lc, l, m, v); build(rc, m+1, r, v); seg[pos] = merge(seg[lc], seg[rc]); } void build(vector<Elm> &v) {build(1, 0, sz-1, v);} void update(int pos, int l, int r, int ul, int ur, Elm val) { if (l > r || ul > ur || ul > r || l > ur) {return;} if (ul <= l && r <= ur) { updateNode(pos, val); return; } checkLazy(pos, l, r); update(lc, l, m, ul, ur, val); update(rc, m+1, r, ul, ur, val); seg[pos] = merge(seg[lc], seg[rc]); } void update(int ul, int ur, Elm val) {update(1, 0, sz-1, ul, ur, val);} Elm query(int pos, int l, int r, int ql, int qr) { if (l > r || ql > qr || ql > r || l > qr) {return DEFAULT;} if (ql <= l && r <= qr) {return seg[pos];} checkLazy(pos, l, r); return merge(query(lc, l, m, ql, qr), query(rc, m+1, r, ql, qr)); } Elm query(int ql, int qr) {return query(1, 0, sz-1, ql, qr);} #undef m #undef lc #undef rc }; ostream& operator<<(ostream &os, SegtreeLazy &S) { for (int i = 0; i < S.sz; i++) os << S.query(i, i) << ' '; return os; } struct FenwickTree { using Elm = int; int sz; vector<Elm> BIT; FenwickTree(int sz = 1) : sz(sz) { BIT.assign(sz+1, 0); } void update(int idx, Elm val) { idx++; for (; idx <= sz; idx += (idx & -idx)) {BIT[idx] += val;} } Elm sum(int idx) { idx++; Elm ret = 0; for (; idx > 0; idx -= (idx & -idx)) {ret += BIT[idx];} return ret; } Elm query(int l, int r) {return sum(r) - sum(l-1);} }; SegtreeLazy G_Pref, G_Suff, L_Pref, L_Suff; FenwickTree Gr, Le; bool check(int l, int r, int N, vector<int> &A, int val) { int gr = Gr.query(l, r), le = Le.query(l, r); int len = r - l + 1; int eq = len - gr - le; bool needGreater = (gr < le); int target = abs(gr - le) - eq; // cout << l << ' ' << r << '\n'; // cout << gr << ' ' << le << ' ' << eq << '\n'; // debug(needGreater); // debug(target); // cout << "---\n"; int cur = 0; int LL = N-l, RL = r+1; if (needGreater) { int cl = 0, cr = 0; if (l > 0) cl = G_Suff.query(0, l) - LL + 2*Le.query(l, N-1); if (r < N-1) cr = G_Pref.query(r, N-1) - RL + 2*Le.query(0, r); // debug(G_Suff); debug(G_Pref); // debug(cl); debug(cr); cur = max(cur, cl + cr); } else { int cl = 0, cr = 0; if (l > 0) cl = L_Suff.query(0, l) - LL + 2*Gr.query(l, N-1); if (r < N-1) cr = L_Pref.query(r, N-1) - RL + 2*Gr.query(0, r); // debug(L_Suff); debug(L_Pref); // debug(cl); debug(cr); cur = max(cur, cl + cr); } // cout << '\n'; return (cur >= target); } int sequence(int N, std::vector<int> A) { vector<vector<int>> occ(N+1); for (int i = 0; i < N; i++) occ[A[i]].push_back(i); // Greater = +1 // Less = -1 G_Pref = G_Suff = L_Pref = L_Suff = SegtreeLazy(N); Gr = Le = FenwickTree(N); // Initially, everything is greater vector<int> init(N); for (int i = 0; i < N; i++) init[i] = i + 1; G_Pref.build(init); Reverse(init); G_Suff.build(init); for (auto &i : init) i *= -1; L_Suff.build(init); Reverse(init); L_Pref.build(init); for (int i = 0; i < N; i++) Gr.update(i, 1); int ans = 1; for (int i = 1; i <= N; i++) { if (occ[i].empty()) continue; // Turn i to less in LSkew for (auto j : occ[i]) L_Pref.update(j, N-1, 2); for (auto j : occ[i]) L_Suff.update(0, j, 2); for (auto j : occ[i]) Gr.update(j, -1); int cs = (int)occ[i].size(); for (int pl = 0, pr = -1; pl < cs; pl++) { while (pr + 1 < cs) { if (check(occ[i][pl], occ[i][pr+1], N, A, i)) pr++; else break; } ans = max(ans, pr - pl + 1); } // Turn i to less in GSkew for (auto j : occ[i]) G_Pref.update(j, N-1, -2); for (auto j : occ[i]) G_Suff.update(0, j, -2); for (auto j : occ[i]) Le.update(j, 1); } return ans; } #ifdef Zanite int main() { int N; assert(1 == scanf("%d", &N)); std::vector<int> A(N); for (int i = 0; i < N; ++i) { assert(1 == scanf("%d", &A[i])); } int result = sequence(N, A); printf("%d\n", result); return 0; } #endif
#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...