Submission #964841

#	Time	Username	Problem	Language	Result	Execution time	Memory
964841		efedmrlr	Rope (JOI17_rope)	C++17	100 / 100	1099 ms	143320 KiB

rope

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;

struct SegT {
    vector<int> dt;
    int n;
    void reset(int s) {
        n = s;
        dt.assign(2*n, 0);
    }
    void build() {
        for(int i = n - 1; i>=1; i--) {
            dt[i] = max(dt[i << 1], dt[i << 1 ^ 1]);
        }
    }

    void update(int ind, int val) {
        ind += n;
        for(dt[ind] += val; ind > 1; ind >>= 1) dt[ind >> 1] = max(dt[ind], dt[ind ^ 1]);          
    }
    int query(int l, int r) {
        // [l, r)
        int ret = 0;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) ret = max(ret, dt[l++]);
            if(r & 1) ret = max(ret, dt[--r]); 
        }
        return ret;
    }
    int query() {
        return query(0, n);
    }
};

vector<int> a;
vector<int> cnt;
vector<vector<int> > pr1, pr2;
SegT st;
int n,m,q;

inline void solve() {
    cin>>n>>m;
    a.resize(n + 5);
    cnt.assign(m + 5, 0);
    pr1.assign(m + 5, vector<int>());
    pr2.assign(m + 5, vector<int>());
    st.reset(m + 3);
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    } 
    for(int i = 1; i<=n; i++) {
        cnt[a[i]]++;
    }
    for(int i = 1; i<n; i+=2) {
        if(a[i] == a[i + 1]) continue;
        pr1[a[i]].pb(a[i + 1]);
        pr1[a[i + 1]].pb(a[i]);
    }
    for(int i = 2; i<n; i+=2) {
        if(a[i] == a[i + 1]) continue; 
        pr2[a[i]].pb(a[i + 1]);
        pr2[a[i + 1]].pb(a[i]);
        
    }
    for(int i = 1; i<=m; i++) {
        st.dt[i + st.n] = cnt[i];
    }
    st.build();
    vector<int> res(m + 1, INF);
    for(int i = 1; i<=m; i++) {
        res[i] = n - cnt[i];
    }
    
    for(int i = 1; i<=m; i++) {
        // Case 1
        for(auto c : pr1[i]) {
            st.update(c, -1);
        }
        st.update(i, -cnt[i]);
        res[i] = min(res[i], n - (cnt[i] + st.query()));

        for(auto c : pr1[i]) {
            st.update(c, 1);
        }

        // Case 2
        for(auto c : pr2[i]) {
            st.update(c, -1);
        }
        res[i] = min(res[i], n - (cnt[i] + st.query()));
        st.update(i, cnt[i]);
        for(auto c : pr2[i]) {
            st.update(c, 1);
        }
    }
    for(int i = 1; i<=m; i++) {
        cout << res[i] << "\n";
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

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