Submission #758195

#TimeUsernameProblemLanguageResultExecution timeMemory
758195PixelCatRope (JOI17_rope)C++14
100 / 100
2314 ms202200 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); } #ifdef NYAOWO int64_t LAST_TIMER = -1; inline void timer() { auto now = clock(); if (LAST_TIMER != -1) { cerr << "Elapsed: " << (double)(now - LAST_TIMER) / CLOCKS_PER_SEC << " s\n"; } else { cerr << fixed << setprecision(3); } LAST_TIMER = now; } #else #define timer() #endif const int MAXN = 1000010; int ans[MAXN]; int cnt1[MAXN]; int owo[MAXN]; struct Ayaya { priority_queue<int, vector<int>, greater<int>> pq, gg; Ayaya(int n) { memset(owo, 0, sizeof(owo)); For(i, 1, n) pq.emplace(0); } void add(int i, int x) { gg.emplace(owo[i]); owo[i] += x; pq.emplace(owo[i]); } int min() { while(sz(gg) && pq.top() == gg.top()) { pq.pop(); gg.pop(); } return pq.top(); } }; vector<int> vv[MAXN]; void solve(int n, int m, vector<pii> v2, vector<int> v1) { timer(); memset(cnt1, 0, sizeof(cnt1)); For(i, 1, m) vv[i].clear(); Ayaya aya(m); timer(); for(auto &i:v2) { cnt1[i.F]++; cnt1[i.S]++; vv[i.F].eb(i.S); vv[i.S].eb(i.F); } For(c2, 1, m) aya.add(c2, n - cnt1[c2]); timer(); 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); } timer(); } 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...