제출 #1131409

#제출 시각아이디문제언어결과실행 시간메모리
1131409duckindogSequence (APIO23_sequence)C++17
7 / 100
767 ms64348 KiB
#include <bits/stdc++.h> using namespace std; #ifndef LOCAL #include "sequence.h" #endif const int N = 500'000 + 10; int n; int a[N]; vector<int> pos[N]; namespace IT { struct Node { int mi, ma; Node() : mi(1'000'000'000), ma(0) {} Node(int mi, int ma) : mi(mi), ma(ma) {} } f[N << 2]; int lazy[N << 2]; inline Node merge(const Node& lt, const Node& rt) { return Node(min(lt.mi, rt.mi), max(lt.ma, rt.ma)); } void build(int s, int l, int r) { f[s] = Node(0, 0); lazy[s] = 0; if (l == r) return; int mid = (l + r) >> 1; build(s << 1, l, mid); build(s << 1 | 1, mid + 1, r); } void push(int s) { if (!lazy[s]) return; f[s << 1].mi += lazy[s]; f[s << 1 | 1].mi += lazy[s]; f[s << 1].ma += lazy[s]; f[s << 1 | 1].ma += lazy[s]; lazy[s << 1] += lazy[s]; lazy[s << 1 | 1] += lazy[s]; lazy[s] = 0; } void update(int s, int l, int r, int u, int v, int x) { if (v < l || u > r) return; if (u <= l && r <= v) { f[s].mi += x; f[s].ma += x; lazy[s] += x; return; } push(s); int mid = (l + r) >> 1; update(s << 1, l, mid, u, v, x); update(s << 1 | 1, mid + 1, r, u, v, x); f[s] = merge(f[s << 1], f[s << 1 | 1]); } Node query(int s, int l, int r, int u, int v) { if (v < l || u > r) return Node(); if (u <= l && r <= v) return f[s]; int mid = (l + r) >> 1; return merge(query(s << 1, l, mid, u, v), query(s << 1 | 1, mid + 1, r, u, v)); } } IT::Node saveL[N], saveR[N]; int sequence(int inN, std::vector<int> inA) { { // input n = inN; for (int i = 1; i <= n; ++i) a[i] = inA[i - 1]; } for (int i = 1; i <= n; ++i) pos[i] = {0}; for (int i = 1; i <= n; ++i) pos[a[i]].push_back(i); { // init dist arr IT::build(1, 1, n); for (int i = 1; i <= n; ++i) IT::update(1, 1, n, i, n, 1); for (int index = 1; index <= n; ++index) { for (int i = 1; i < (int)pos[index].size(); ++i) IT::update(1, 1, n, pos[index][i], n, -1); for (int i = 1; i < (int)pos[index].size(); ++i) { int p = pos[index][i]; saveL[p] = IT::query(1, 1, n, 1, p); saveR[p] = IT::query(1, 1, n, p, n); } for (int i = 1; i < (int)pos[index].size(); ++i) IT::update(1, 1, n, pos[index][i], n, -1); } } auto chk = [&](int length) { for (int index = 1; index <= n; ++index) { for (int i = 1; i <= (int)pos[index].size() - length; ++i) { int l = pos[index][i], r = pos[index][i + length - 1]; if (max(saveL[l].mi, saveR[r].mi) - min(saveL[l].ma, saveR[r].ma) <= length) return true; } } return false; }; int le = 1, ri = n, answer = 1; while (le <= ri) { int mid = (le + ri) >> 1; if (chk(mid)) le = (answer = mid) + 1; else ri = mid - 1; } return answer; } #ifdef LOCAL 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...