Submission #686686

#	Time	Username	Problem	Language	Result	Execution time	Memory
686686		JooDdae	Rope (JOI17_rope)	C++17	100 / 100	2106 ms	85012 KiB

rope

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define mid ((l+r) >> 1)

const int INF = 1e9;

int n, m, a[1001001], c[1001001];
vector<array<int, 2>> v[1001001];

int t[4004004];

void update(int id, int x, int node = 1, int l = 1, int r = n) {
    if(id < l || r < id) return;
    if(l == r) {
        t[node] += x;
        return;
    }
    update(id, x, node*2, l, mid), update(id, x, node*2+1, mid+1, r);
    t[node] = max(t[node*2], t[node*2+1]);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) c[a[i]]++;
    for(int i=1;i<=m;i++) update(i, c[i]);

    for(int i=1;i<=n;i++) {
        int j = i;
        while(j < n && a[j+1] == a[j]) j++;
        v[a[i]].push_back({i, j}), i = j;
    }

    for(int i=1;i<=m;i++) {
        int ans = n-c[i];

        update(i, -INF);
        {
            int p = 0, p2 = 0;
            for(auto [L, R] : v[i]) { // [0, 1]
                if(L != 1 && L%2 != 0) L--, p++, update(a[L], -1);
                if(R != n && R%2 != 1) R++, p++, update(a[R], -1);
                p2 += R-L+1;
            }
            ans = min(ans, p+n-p2-t[1]);
            for(auto [L, R] : v[i]) { // [0, 1]
                if(L != 1 && L%2 != 0) L--, update(a[L], 1);
                if(R != n && R%2 != 1) R++, update(a[R], 1);
            }
        }
        {
            int p = 0, p2 = 0;
            for(auto [L, R] : v[i]) { // [1, 0]
                if(L != 1 && L%2 != 1) L--, p++, update(a[L], -1);
                if(R != n && R%2 != 0) R++, p++, update(a[R], -1);
                p2 += R-L+1;
            }
            ans = min(ans, p+n-p2-t[1]);
            for(auto [L, R] : v[i]) { // [0, 1]
                if(L != 1 && L%2 != 1) L--, update(a[L], 1);
                if(R != n && R%2 != 0) R++, update(a[R], 1);
            }
        }

        update(i, INF);

        cout << ans << "\n";
    }
}

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