Submission #758153

#TimeUsernameProblemLanguageResultExecution timeMemory
758153PixelCatRope (JOI17_rope)C++14
55 / 100
2555 ms127584 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; void solve(int n, int m, vector<pii> v2, vector<int> v1) { memset(cnt1, 0, sizeof(cnt1)); map<pii, int> cnt2; for(auto &i:v2) { cnt1[i.F]++; cnt1[i.S]++; cnt2[i]++; cnt2[pii(i.S, i.F)]++; } vector<vector<pii>> vv(m + 1, vector<pii>()); for(auto &i:cnt2) { vv[i.F.F].eb(i.F.S, i.S); } aya.init(m); For(c2, 1, m) aya.upd(c2, n - cnt1[c2]); // 2, 2 // 2 1, 1 3, 3 2, 1 1 // 2 2, 1 1, 3 3, 2 1, 1 2 For(c1, 1, m) { int add = 0; for(auto &p:vv[c1]) { aya.add(p.F, p.S); } for(auto &i:v1) { aya.add(i, -1); if(i == c1) add--; } aya.add(c1, INF); chmin(ans[c1], aya.min() - cnt1[c1] + add); // cout << aya.min() << ", " << add << ", " << (aya.min() - cnt1[c1] + add) << ": "; // For(c2, 1, m) cout << (aya.a[c2] >= INF ? -1 : aya.a[c2]) << " \n"[c2 == m]; aya.add(c1, -INF); for(auto &i:v1) aya.add(i, 1); for(auto &p:vv[c1]) aya.add(p.F, -p.S); // For(c2, c1 + 1, m) { // int cost = n - cnt1[c1] - cnt1[c2]; // if(cnt2.count(pii(c1, c2))) cost += cnt2[pii(c1, c2)]; // for(auto &i:v1) { // cost -= max(i == c1, i == c2); // } // chmin(ans[c1], cost); // chmin(ans[c2], cost); // } int cost = n - cnt1[c1]; for(auto &i:v1) cost -= (i == c1); chmin(ans[c1], cost); } } 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...