Submission #757064

#	Time	Username	Problem	Language	Result	Execution time	Memory
757064		1bin	Rope (JOI17_rope)	C++14	100 / 100	935 ms	76620 KiB

rope

#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 1e6 + 5;
int n, m, a[NMAX], C[NMAX], cnt[NMAX], mx, ans;
vector<int> v[NMAX];

void add(int c, int f){
    cnt[C[c]]--;
    if(!f){
        cnt[--C[c]]++;
        if(!cnt[mx]) mx--;
    }
    else{
        cnt[++C[c]]++;
        if(cnt[mx + 1]) mx++;
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    cnt[0] = m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        add(a[i], 1);
        v[a[i]].emplace_back(i);
    }
    
    for(int c = 1; c <= m; c++){
        for(int i = 0; i < v[c].size(); i++) add(c, 0);
        ans = 1e9;
        for(int f = 0; f < 2; f++){
            int ret = n - v[c].size();
            for(int& ix : v[c]){
                if((ix & 1) == f){
                    if(ix + 1 < n && a[ix + 1] != c) add(a[ix + 1], 0);
                }
                else{
                    if(ix && a[ix - 1] != c) add(a[ix - 1], 0);
                }
            }
            ans = min(ans, ret - mx);
            
            for(int& ix : v[c]){
                if((ix & 1) == f){
                    if(ix + 1 < n && a[ix + 1] != c) add(a[ix + 1], 1);
                }
                else{
                    if(ix && a[ix - 1] != c) add(a[ix - 1], 1);
                }
            }
        }
        cout << ans << '\n';
        for(int i = 0; i < v[c].size(); i++) add(c, 1);
    }
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:36:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int i = 0; i < v[c].size(); i++) add(c, 0);
      |                        ~~^~~~~~~~~~~~~
rope.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for(int i = 0; i < v[c].size(); i++) add(c, 1);
      |                        ~~^~~~~~~~~~~~~

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