Submission #1173678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173678		LucaIlie	Rope (JOI17_rope)	C++20	100 / 100	529 ms	134240 KiB

rope

#include <bits/stdc++.h>

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

using namespace std;

const int MAX_N = 1e6;
const int MAX_M = 1e6;
int c[MAX_N], frecv[MAX_M + 1];
vector<int> pos[MAX_M + 1];
priority_queue<pair<int, int>> pq;

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++ ) 
        pq.push( { frecv[i], 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 ) {
                    frecv[c[q]]--;
                    sumFrecv--;
                    pq.push( { frecv[c[q]], c[q] } );
                    changes++;
                }
            }

            auto maxx = pq.top();
            while ( frecv[maxx.second] != maxx.first ) {
                pq.pop();
                maxx = pq.top();
            }
            auto maxx2 = maxx;
            while ( frecv[maxx2.second] != maxx2.first || maxx2.second == x ) {
                pq.pop();
                maxx2 = pq.top();
            }

            changes += sumFrecv - maxx2.first;
            if ( maxx.second == x )
                pq.push( maxx );

            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 ) {
                    frecv[c[q]]++;
                    pq.push( { frecv[c[q]], 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: 20 / 20