Submission #1185724

#TimeUsernameProblemLanguageResultExecution timeMemory
1185724Gurban서열 (APIO23_sequence)C++20
32 / 100
446 ms47944 KiB
/** * In the name of Allah * We are nothing and you're everything **/ #include <bits/stdc++.h> #include "sequence.h" #define all(x) x.begin(), x.end() #define sz(x) (int)x.size() //#define int long long const int mod = 1e9+9; using namespace std; using ll = long long; const int inf = 1e9+7; pair<int, int> neutral = {inf, -inf}; pair<int, int> operator+(const pair<int, int> &a, const pair<int, int> &b) { return {min(a.first, b.first), max(a.second, b.second)}; } struct segtree { vector<pair<int, int>> tree; vector<int> gos; int size = 1; void init(int n) { //size = 1; while (size < n)size <<= 1; tree.assign(2*size-1, {0, 0}); gos.assign(2*size-1, 0); } void apply(int l, int r, int v, int x, int lx, int rx) { if (rx <= l || r <= lx)return; if (lx >= l && rx <= r) { gos[x] += v; tree[x].first += v, tree[x].second += v; return; } int mid = lx + rx >> 1; apply(l, r, v, 2*x+1, lx, mid), apply(l, r, v, 2*x+2, mid, rx); tree[x] = tree[2*x+1]+tree[2*x+2]; tree[x].first += gos[x], tree[x].second += gos[x]; } void apply(int l, int r, int v) { apply(l, r, v, 0, 0, size); } pair<int, int> get(int l, int r, int x, int lx, int rx) { if (rx <= l || r <= lx)return neutral; if (lx >= l && rx <= r)return tree[x]; int mid = lx + rx >> 1; pair<int, int> s1 = get(l, r, 2*x+1, lx, mid) + get(l, r, 2*x+2, mid, rx); s1.first += gos[x], s1.second += gos[x]; return s1; } pair<int, int> get(int l, int r) { return get(l, r, 0, 0, size); } }; int sequence(int n, vector<int> a) { vector<pair<int, int>> cnt(n+1, {-1, -1}); for (int i = 0; i < n; ++i) { int x = a[i]; if (cnt[x].first == -1)cnt[x].first = i; else cnt[x].second = i; } vector<int> adj[n+1]; for (int i = 0; i < n; ++i) adj[a[i]].push_back(i); segtree st; st.init(n+1); for (int i = 0; i < n; ++i) { st.apply(i, n, 1); } int ans = 1; for (int i = 1; i <= n; ++i) { int x = i; if (sz(adj[x]) <= ans) { for (auto j: adj[x]) st.apply(j, n, -2); continue; } for (int j:adj[x]) st.apply(j, n, -1); for (int j = sz(adj[x])-1; j >= 0; --j) { while (j + ans < sz(adj[x])) { pair<int, int> l = st.get(0, adj[i][j]); pair<int, int> r = st.get(adj[i][j+ans], n); if (r.first >= -ans-1 && r.first <= ans+1) { ans += 1; continue; } if (r.second >= -ans-1 && r.second <= ans+1) { ans += 1; continue; } l.first -= (ans+1), l.second += ans+1; if (max(l.first, r.first) <= min(r.second, l.second))ans++; else break; } } for (auto j: adj[x]) st.apply(j, n, -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...