제출 #1047932

#제출 시각아이디문제언어결과실행 시간메모리
1047932BABY_GANGSTER서열 (APIO23_sequence)C++17
100 / 100
460 ms80972 KiB
#include <bits/stdc++.h> #include "sequence.h" using namespace std; struct Segtree { struct Node { int64_t max_prefix_sum, max_suffix_sum, range_sum; Node() { memset(this, 0, sizeof *this); } }; vector<Node> t; size_t l; Segtree(size_t n) { l = 1 << (32 - __builtin_clz(n)); t.resize(2 * l); } Node combine(Node const &x, Node const &y) { Node z; z.max_prefix_sum = max(x.max_prefix_sum, x.range_sum + y.max_prefix_sum); z.max_suffix_sum = max(y.max_suffix_sum, y.range_sum + x.max_suffix_sum); z.range_sum = x.range_sum + y.range_sum; return z; } void update(int i, int x) { i += l; t[i].max_prefix_sum = max(0, x); t[i].max_suffix_sum = max(0, x); t[i].range_sum = x; while (i >>= 1) t[i] = combine(t[i << 1], t[i << 1 | 1]); } Node query(int i, int j) { i += l, j += l; Node x = Node(), y = Node(); while (i <= j) { if (i & 1) x = combine(x, t[i++]); if (!(j & 1)) y = combine(t[j--], y); i >>= 1; j >>= 1; } return combine(x, y); } }; int sequence(int N, vector<int> A) { for (int &x : A) --x; vector<vector<int>> occ(N); for (int i = 0; i < N; ++i) occ[A[i]].push_back(i); Segtree tree_ge(N), tree_le(N); for (int i = 0; i < N; ++i) tree_ge.update(i, 1), tree_le.update(i, -1); int ans = 0; for (int i = 0; i < N; ++i) { for (int &j : occ[i]) tree_le.update(j, 1); auto jt = occ[i].begin(); for (auto it = occ[i].begin(); it != occ[i].end(); ++it) { if (jt < it) jt = it; while (jt + 1 != occ[i].end()) { if ((tree_ge.query(*it, *(jt + 1)).range_sum + tree_ge.query(0, *it - 1).max_suffix_sum + tree_ge.query(*(jt + 1) + 1, N - 1).max_prefix_sum) * (tree_le.query(*it, *(jt + 1)).range_sum + tree_le.query(0, *it - 1).max_suffix_sum + tree_le.query(*(jt + 1) + 1, N - 1).max_prefix_sum) >= 0) ++jt; else break; } ans = max(ans, (int)(jt - it + 1)); } for (int &j : occ[i]) tree_ge.update(j, -1); } return ans; }
#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...