Submission #1173671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173671		LucaIlie	Rope (JOI17_rope)	C++20	80 / 100	2597 ms	116948 KiB

rope

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6;
const int MAX_M = 1e6;
int c[MAX_N], ans[MAX_M + 1], frecv[MAX_M + 1];
vector<int> pos[MAX_M + 1];
set<pair<int, int>> maxFrecv;

void erase( int col ) {
    maxFrecv.erase( { frecv[col], col } );
}

void insert( int col ) {
    maxFrecv.insert( { frecv[col], col } );
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n, m;

    cin >> n >> m;
    for ( int i = 0; i < n; i++ ) {
        cin >> c[i];
        frecv[c[i]]++;
        pos[c[i]].push_back( i );
    }

    if ( m == 1 ) {
        cout << "0\n";
        return 0;
    }

    for ( int i = 1; i <= m; i++ )
        insert( i );

    for ( int x = 1; x <= m; x++ ) {
        int minn = n;
        for ( int f = 0; f < 2; f++ ) {
            int changes = 0, sumFrecv = n - frecv[x];
            for ( int p: pos[x] ) {
                int q = ((p - f) % 2 == 0 ? p + 1 : p - 1);
                if ( f <= q && q < n && c[q] != x ) {
                    erase( c[q] );
                    frecv[c[q]]--;
                    sumFrecv--;
                    insert( c[q] );
                    changes++;
                }
            }

            auto p = maxFrecv.end();
            p--;
            if ( p->second == x )
                p--;

            changes += sumFrecv - p->first;

            minn = min( minn, changes );

            for ( int p: pos[x] ) {
                int q = ((p - f) % 2 == 0 ? p + 1 : p - 1);
                if ( f <= q && q < n && c[q] != x ) {
                    erase( c[q] );
                    frecv[c[q]]++;
                    insert( c[q] );
                }
            }
       }

        cout << minn << "\n";
    }

    return 0;
}

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