제출 #1095100

#제출 시각아이디문제언어결과실행 시간메모리
1095100RiverFlow서열 (APIO23_sequence)C++17
48 / 100
409 ms91788 KiB
#include <bits/stdc++.h> #define nl "\n" #define no "NO" #define yes "YES" #define fi first #define se second #define vec vector #define task "main" #define _mp make_pair #define ii pair<int, int> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define evoid(val) return void(std::cout << val) #define FOR(i, a, b) for(int i = (a); i <= (b); ++i) #define FOD(i, b, a) for(int i = (b); i >= (a); --i) #define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin()) using namespace std; template<typename U, typename V> bool maxi(U &a, V b) { if (a < b) { a = b; return 1; } return 0; } template<typename U, typename V> bool mini(U &a, V b) { if (a > b) { a = b; return 1; } return 0; } const int N = (int)5e5 + 7; int n, a[N]; namespace SUB1 { struct CTDL { multiset<int> a, b; void add(int x) { if (sz(a) <= sz(b)) a.insert(x); else b.insert(x); if (sz(a) and sz(b) and *a.rbegin()>*b.begin()){ int x=*a.rbegin(), y=*b.begin(); a.erase(a.find(x)); b.erase(b.find(y)); a.insert(y); b.insert(x); } } int med() { return *a.rbegin(); } int med2() { return *b.begin(); } }; int sol() { int ans = 0; vec<int> cnt(n + 1, 0); FOR(i, 1, n) { CTDL s; FOR(j, i, n) { ++cnt[a[j]]; s.add(a[j]); ans = max(ans, cnt[s.med()]); if ( (j - i + 1) % 2 == 0 ) ans = max(ans, cnt[s.med2()]); } FOR(j, i, n) { --cnt[a[j]]; } } return ans; } }; namespace SUB2 { bool check() { vec<bool> okl(n + 1, 0), okr(n + 1, 0); okl[1] = 1; FOR(i, 2, n) { okl[i] = okl[i - 1] and (a[i] >= a[i-1]); } okr[n] = 1; FOD(i, n - 1, 1) { okr[i] = okr[i + 1] and (a[i] >= a[i + 1]); } FOR(i, 1, n) { if (okl[i] and okr[i]) return 1; } return 0; } int sol() { int ans = 0; vec<int> cnt(n + 1, 0); vec<ii> b; FOR(i, 1, n) { int j = i; while (j + 1 <= n and a[j + 1] == a[i]) ++j; b.push_back(_mp(a[i], j - i + 1)); cnt[a[i]] += j - i + 1; ans = max(ans, j - i + 1); i = j; } sort(all(b)); int g = 0; for(int i = sz(b) - 1; i >= 0; --i) { ii j = b[i]; int v = j.fi, c = j.se; if (c!=cnt[v]) { int k=g; int p=cnt[v]; int j=n-(k+p); if (j >= k - p) { ans = max(ans, cnt[v]); } // cerr << v << ' ' << k << ' ' << p << ' ' << j << nl; } g+=cnt[v]; if (i > 0 and b[i].fi==b[i-1].fi) --i; } return ans; } }; namespace SUB5 { struct IT { int n; vec<ii> t; vec<int> lz; IT (){}; IT (int _n) { n = _n; lz.resize(4 * n + 7); t.resize(4 * n + 7); } vec<int> a; void refine(int id) { t[id].fi = min(t[id << 1].fi, t[id << 1 | 1].fi); t[id].se = max(t[id << 1].se, t[id << 1 | 1].se); } void build(int id, int l, int r) { if (l == r) { return void(t[id]=_mp(a[l], a[l])); } int m = (l + r) >> 1; build(id << 1, l, m); build(id << 1 | 1, m + 1, r); refine(id); } void init(vec<int> p){ a.resize(n + 1); FOR(i, 1, n) a[i] = p[i]; build(1, 1, n); } void push(int id) { int &x = lz[id]; t[id<<1].fi+=x; t[id<<1|1].fi+=x; t[id<<1].se+=x; t[id<<1|1].se+=x; lz[id<<1]+=x; lz[id<<1|1]+=x; x=0; } void update(int id, int l, int r, int u, int v, int val) { if (l > v or r < u) return ; if (l >= u and r <= v) { t[id].fi += val; t[id].se += val; lz[id] += val; return ; } if (lz[id]) { push(id); } int m = (l + r) >> 1; update(id << 1, l, m, u, v, val); update(id << 1 | 1, m + 1, r, u, v, val); refine(id); } void update(int l, int r, int v) { if (l > r) return ; update(1, 1, n, l, r, v); } ii get(int id, int l, int r, int u, int v) { if (l > v or r < u) { return _mp(n, -n); } if (l >= u and r <= v) return t[id]; if (lz[id]) { push(id); } int m = (l + r) >> 1; ii A = get(id << 1, l, m, u, v); ii B = get(id << 1 | 1, m + 1, r, u, v); return _mp(min(A.fi, B.fi), max(A.se, B.se)); } ii get(int l, int r) { return get(1, 1, n, l, r); } }; vec<int> pos[N]; bool check() { vec<int> cnt(n + 1, 0); FOR(i, 1, n) ++cnt[a[i]]; if (*max_element(all(cnt)) > 2) return 0; return 1; } int sol() { FOR(i, 1, n - 1) if (a[i] == a[i+1]) return 2; int ans = 1; FOR(i, 1, n) { pos[a[i]].push_back(i); } IT st1(n), st2(n); vec<int> p(n+1,0); FOR(i,1,n)p[i]=-(i-1); st1.init(p); // pref(l-1) FOR(i,1,n)p[i]=-i; st2.init(p); // pref(r) FOR(i, 1, n) if (sz(pos[i])) { if (sz(pos[i]) == 2) { int x = pos[i][0], y = pos[i][1]; ii A = st1.get(1,x); assert(A.fi <= A.se); // cerr << A.fi << ' ' << A.se<< nl; A.fi-=4; ii B = st2.get(y,n); // cerr << B.fi << ' ' << B.se << nl; // cerr << x << ' ' << y << nl; if (!(A.fi > B.se or A.se < B.fi)) { ans=2; return ans; } } for(int j : pos[i]) { //pref(j+1) duoc cong them 2 st1.update(j + 1, n, 2); st2.update(j, n, 2); } } return 1; } }; int sequence(int N, vector<int> A) { n = N; FOR(i, 1, n) a[i] = A[i - 1]; if (n <= 2000) { return SUB1::sol(); } if (SUB2::check()) { return SUB2::sol(); } if (SUB5::check()) { return SUB5::sol(); } return 0; } #ifdef LOCAL int main() { ios::sync_with_stdio(0); cin.tie(0); freopen("main.inp", "r", stdin); freopen("main.out", "w", stdout); int n; cin >> n; vector<int> a(n); for(int & x : a) cin >> x; cout << sequence(n, a); } #endif LOCAL

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp:278:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  278 | #endif LOCAL
      |        ^~~~~
#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...