Submission #46715

#TimeUsernameProblemLanguageResultExecution timeMemory
46715qoo2p5Rope (JOI17_rope)C++17
0 / 100
90 ms91156 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int INF = (int) 1e9 + 1e6 + 123; const ll LINF = (ll) 1e18 + 1e9 + 123; #define rep(i, s, t) for (auto i = (s); i < (t); ++(i)) #define per(i, s, t) for (auto i = (s); i >= (t); --(i)) #define all(x) (x).begin(), (x).end() #define sz(x) ((int)(x).size()) #define mp make_pair #define pb push_back bool mini(auto &x, const auto &y) { if (y < x) { x = y; return 1; } return 0; } bool maxi(auto &x, const auto &y) { if (y > x) { x = y; return 1; } return 0; } void run(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); run(); return 0; } const int N = 1 << 20; int n, m; int a[N]; int tree[2 * N]; int cnt_full[N]; vector<int> match[N]; int bonus[N]; void clr() { memset(bonus, 0, sizeof bonus); memset(tree, 0, sizeof tree); memset(cnt_full, 0, sizeof cnt_full); rep(i, 0, N) { match[i].clear(); } } void add(int i, int tl, int tr, int ind, int val) { if (tl == tr - 1) { tree[i] += val; return; } int tm = (tl + tr) / 2; if (ind < tm) add(2 * i + 1, tl, tm, ind, val); else add(2 * i + 2, tm, tr, ind, val); tree[i] = max(tree[2 * i + 1], tree[2 * i + 2]); } void add(int ind, int val) { add(0, 0, N, ind, val); } int get(int i, int tl, int tr, int l, int r) { if (tl >= r || tr <= l) { return -INF; } if (l <= tl && tr <= r) { return tree[i]; } int tm = (tl + tr) / 2; return max(get(2 * i + 1, tl, tm, l, r), get(2 * i + 2, tm, tr, l, r)); } int get(int l, int r) { return get(0, 0, N, l, r + 1); } int ans[N]; void run() { cin >> n >> m; rep(i, 0, n) { cin >> a[i]; a[i]--; } rep(i, 0, N) { ans[i] = INF; } rep(odd_l, 0, 2) { rep(odd_r, 0, 2) { if ((odd_l + odd_r) % 2 != n % 2) { continue; } rep(who_l, 0, 2) { rep(who_r, 0, 2) { clr(); if (odd_l) { if (who_l) { bonus[a[0]]++; } else { add(a[0], 1); } } if (odd_r) { if (who_r) { bonus[a[n - 1]]++; } else { add(a[n - 1], 1); } } for (int i = odd_l; i < n - odd_r; i += 2) { if (a[i] != a[i + 1]) { match[a[i]].pb(a[i + 1]); match[a[i + 1]].pb(a[i]); } else { cnt_full[a[i]]++; } } rep(i, 0, m) { for (int j : match[i]) { add(i, 1); } add(i, 2 * cnt_full[i]); } rep(i, 0, m) { int we = bonus[i] + cnt_full[i] * 2; int simple = 0; for (int j : match[i]) { add(j, -1); we++; simple++; } int other = max(get(0, i - 1), get(i + 1, m - 1)); assert(other >= 0); if (other == 0) { if (simple > 0) { we--; other++; } else if (bonus[i] > 0) { we--; other++; } else { //assert(false); we = 0; other = 0; } } mini(ans[i], n - (we + other)); for (int j : match[i]) { add(j, 1); } } } } } } rep(i, 0, m) { cout << ans[i] << "\n"; } }

Compilation message (stderr)

rope.cpp: In function 'void run()':
rope.cpp:138:34: warning: unused variable 'j' [-Wunused-variable]
                         for (int j : match[i]) {
                                  ^
#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...