제출 #1000744

#제출 시각아이디문제언어결과실행 시간메모리
1000744vuavisao9월 (APIO24_september)C++17
34 / 100
1012 ms28568 KiB
#include "september.h" #include <vector> #include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; const int INF = 1'000'000'000; const uint8_t size_T = 2; const int _1hrd = 100; const int _1bil = 1000000000; const array<int, size_T> MOD = {_1bil + 9, _1bil + 11}; const array<int, size_T> BASE = {_1hrd + 28, _1hrd + 31}; struct Hash { array<int, size_T> val = {0}; Hash() {}; Hash (int x) { for (uint8_t i = 0; i < size_T; ++ i) this->val[i] = x % MOD[i]; } bool operator < (const Hash& other) const { for (uint8_t i = 0; i < size_T; ++ i) if (this->val[i] != other.val[i]) return this->val[i] < other.val[i]; return false; } bool operator == (const Hash& other) const { for (uint8_t i = 0; i < size_T; ++ i) if (this->val[i] != other.val[i]) return false; return true; } Hash operator + (const int& x) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) res.val[i] = (1ll * this->val[i] * BASE[i] + x) % MOD[i]; return res; } Hash operator + (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) res.val[i] = (this->val[i] + other.val[i]) % MOD[i]; return res; } Hash operator - (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) { res.val[i] = (this->val[i] - other.val[i]) % MOD[i]; res.val[i] = (res.val[i] + MOD[i]) % MOD[i]; } return res; } Hash operator * (const Hash& other) const { Hash res; for (uint8_t i = 0; i < size_T; ++ i) res.val[i] = (1ll * this->val[i] * other.val[i]) % MOD[i]; return res; } friend ostream& operator << (ostream& os, Hash& other) { os << "[ "; for (uint8_t i = 0; i < size_T; ++ i) { cout << other.val[i]; if(i < size_T - 1) cout << ','; cout << ' '; } os << "]"; return os; } }; struct FenWick { int n_node = 0; vector<int> tree = {}; void resize(int n) { n_node = n; tree.resize(n + 10, 0); } FenWick() {}; FenWick(int n) { this->resize(n); }; void Update(int idx, int val) { for ( ; idx <= n_node; idx += (idx & - idx)) tree[idx] += val; return; } int Query(int idx) { int res = 0; for ( ; idx > 0; idx -= (idx & - idx)) res += tree[idx]; return res; } int Sum_to(int l, int r) { if (l > r) return 0; return Query(r) - Query(l - 1); } int kth(int val) { int res = 0, s = 0; for (int mask = 30; mask >= 0; -- mask) { int nxt = res | (1 << mask); if (nxt < n_node && s + tree[nxt] < val) { res = nxt; s += tree[nxt]; } } ++ res; return res; } }; int n, m; int parent[N]; vector<int> g[N]; int perRem[10][N]; int need[10][N]; namespace Order { struct que { int idx; int l, r, mid; que() {}; que(int _idx, int _l, int _r) : idx(_idx), l(_l), r(_r) {}; void reCalculate() { mid = (l + r) >> 1; } bool operator<(const que& other) const { return this->mid < other.mid; } }; int cnt; int in[N], out[N]; void dfs(int u) { in[u] = ++ cnt; for (const auto& v : g[u]) dfs(v); out[u] = cnt; } void solve(int perRem[], int res[]) { cnt = 0; dfs(1); vector<que> qq; for (int i = 1; i < n; ++ i) { qq.push_back(que(i, 1, n - 1)); qq.back().reCalculate(); res[i] = n - 1; } FenWick bit(n); while (!qq.empty()) { vector<que> newQQ; sort(qq.begin(), qq.end()); int last = 1; for (auto& [idx, l, r, mid] : qq) { while (last <= mid) { const auto& u = perRem[last]; bit.Update(in[u], 1); ++ last; } int u = perRem[idx]; if (bit.Sum_to(in[u], out[u]) == out[u] - in[u] + 1) { res[idx] = mid; r = mid - 1; } else { l = mid + 1; } if (l <= r) { newQQ.push_back(que(idx, l, r)); newQQ.back().reCalculate(); } } for (int i = last - 1; i >= 1; -- i) bit.Update(in[perRem[i]], -1); qq = newQQ; } } } namespace One { bool check() { return (m == 1); } struct SegTree { struct Node { int val = -INF; Node() {}; Node(int _val) : val(_val) {}; Node operator + (const Node& other) const { Node res; res.val = max(this->val, other.val); return res; } }; int n_node = 0; vector<Node> tree = {}; void resize(int _n) { n_node = _n; tree.clear(); tree.resize((n_node << 2) + 10); }; SegTree() {}; SegTree(int _n) { this->resize(_n); }; void update(int node, int l, int r, int idx, int val) { if (l == r) { tree[node].val = val; return; } int mid = (l + r) >> 1; if (idx <= mid) update(node << 1, l, mid, idx, val); else update(node << 1 | 1, mid + 1, r, idx, val); tree[node] = tree[node << 1] + tree[node << 1 | 1]; } void Update(int idx, int val) { return update(1, 1, n_node, idx, val); } Node query(int node, int l, int r, int L, int R) { if (l > r || L > R || l > R || L > r) return Node(); if (L <= l && r <= R) return tree[node]; int mid = (l + r) >> 1; return query(node << 1, l, mid, L, R) + query(node << 1 | 1, mid + 1, r, L, R); } Node Query(int l, int r) { return query(1, 1, n_node, l, r); } }; vector<int> open[N]; int dp[N]; int solve() { for (int i = 0; i <= n + 1; ++ i) { vector<int>().swap(open[i]); dp[i] = -INF; } for (int i = 1; i < n; ++ i) { open[need[1][i]].push_back(i); } dp[0] = 0; FenWick bit(n); for (int i = 1; i < n; ++ i) bit.Update(i, 1); SegTree st(n); for (int i = 1; i < n; ++ i) { for (const auto& idx : open[i]) bit.Update(idx, -1); st.Update(i, dp[i - 1]); int cnt = bit.Query(i); int last = bit.kth(cnt) + (cnt != 0); // cout << cnt << ' ' << last << '\n'; if (last <= i) { dp[i] = st.Query(last, i).val + 1; } } return dp[n - 1]; } } // namespace Line { // bool check() { // for (int v = 2; v <= n; ++ v) { // if (parent[v] != v - 1) return false; // } // return true; // } // int calc() { // } // } int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) { n = N; m = M; for (int i = 0; i <= n + 1; ++ i) g[i].clear(); for (int v = 2; v <= n; ++ v) { int u = F[v - 1] + 1; g[u].push_back(v); parent[v] = u; // cerr << u << ' ' << v << '\n'; } for (int i = 0; i < m; ++ i) { for (int j = 0; j < n - 1; ++ j) { perRem[i + 1][j + 1] = S[i][j] + 1; // cerr << i + 1 << ' ' << j + 1 << ' ' << perRem[i + 1][j + 1] << ' ' << S[i][j] << '\n'; } } for (int i = 1; i <= m; ++ i) { Order::solve(perRem[i], need[i]); // for (int j = 1; j <= n; ++ j) cout << need[i][j] << ' '; } // if (OneLine::check()) { // return OneLine::calc(); // } if (One::check()) { return One::solve(); } // if (Line::check()) { // return Line::calc(); // } return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...