Submission #46720

#	Time	Username	Problem	Language	Result	Execution time	Memory
46720		qoo2p5	Rope (JOI17_rope)	C++17	55 / 100	2562 ms	67320 KiB

rope

#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;
    if (m == 1) {
        cout << "0\n";
        return;
    }
    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);
                            }
                        }
                        
                        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:142:34: warning: unused variable 'j' [-Wunused-variable]
                         for (int j : match[i]) {
                                  ^

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20