Submission #758189

#	Time	Username	Problem	Language	Result	Execution time	Memory
758189		PixelCat	Rope (JOI17_rope)	C++14	80 / 100	2585 ms	192780 KiB

rope

#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(x);
    }
    void add(int i, int x) {
        upd(i, a[i] + x);
    }
    int min() {
        return *st.begin();
    }
}; // aya;

struct Ayaya2 {
    int a[MAXN];
    priority_queue<int, vector<int>, greater<int>> pq, gg;
    void init(int n) {
        memset(a, 0, sizeof(a));
        while(!pq.empty()) pq.pop();
        while(!gg.empty()) gg.pop();
        For(i, 1, n) pq.emplace(0);
    }
    void add(int i, int x) {
        gg.emplace(a[i]);
        a[i] += x;
        pq.emplace(a[i]);
    }
    int min() {
        while(sz(gg) && pq.top() == gg.top()) {
            pq.pop(); gg.pop();
        }
        return pq.top();
    }
} 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.add(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;
}

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