Submission #758177

#TimeUsernameProblemLanguageResultExecution timeMemory
758177PixelCatRope (JOI17_rope)C++14
80 / 100
2525 ms155788 KiB
#include <bits/stdc++.h> #define For(i, a, b) for(int i = a; i <= b; i++) #define Forr(i, a, b) for(int i = a; i >= b; i--) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define eb emplace_back #define int LL #define INF (int)(1e18) using namespace std; using LL = long long; using pii = pair<int, int>; void chmin(int &x, int a) { x = min(x, a); } void chmax(int &x, int a) { x = max(x, a); } const int MAXN = 1000010; int ans[MAXN]; int cnt1[MAXN]; struct Ayaya { int a[MAXN]; multiset<int> st; void init(int n) { memset(a, 0, sizeof(a)); st.clear(); For(i, 1, n) st.insert(0); } void upd(int i, int x) { st.erase(st.find(a[i])); a[i] = x; st.insert(a[i]); } void add(int i, int x) { upd(i, a[i] + x); } int min() { return *st.begin(); } } aya; vector<int> vv[MAXN]; void solve(int n, int m, vector<pii> v2, vector<int> v1) { memset(cnt1, 0, sizeof(cnt1)); For(i, 1, m) vv[i].clear(); for(auto &i:v2) { cnt1[i.F]++; cnt1[i.S]++; vv[i.F].eb(i.S); vv[i.S].eb(i.F); } aya.init(m); For(c2, 1, m) aya.upd(c2, n - cnt1[c2]); For(c1, 1, m) { int add = 0; for(auto &p:vv[c1]) aya.add(p, 1); for(auto &i:v1) { aya.add(i, -1); add -= (i == c1); } aya.add(c1, INF); chmin(ans[c1], aya.min() - cnt1[c1] + add); aya.add(c1, -INF); for(auto &i:v1) aya.add(i, 1); for(auto &p:vv[c1]) aya.add(p, -1); chmin(ans[c1], n - cnt1[c1] + add); } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // =^-w-^= int n, m; cin >> n >> m; vector<int> a(n); for(auto &i:a) cin >> i; For(i, 1, m) { ans[i] = INF; } if(n % 2) { For(_, 0, 1) { vector<pii> v2; for(int i = 1; i < n; i += 2) { v2.eb(pii(a[i - 1], a[i])); } solve(n, m, v2, { a.back() }); reverse(all(a)); } } else { vector<pii> v2; for(int i = 1; i < n; i += 2) { v2.eb(pii(a[i - 1], a[i])); } solve(n, m, v2, {}); v2.clear(); for(int i = 2; i < n; i += 2) { v2.eb(pii(a[i - 1], a[i])); } solve(n, m, v2, { a.front(), a.back() }); } For(i, 1, m) cout << ans[i] << "\n"; 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...