Submission #1001069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001069		mispertion	Rope (JOI17_rope)	C++17	100 / 100	2222 ms	210956 KiB

rope

#include<bits/stdc++.h>
 
using namespace std;
 
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
 
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mispertion ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define F first
#define S second
#define getlast(s) (*s.rbegin())
#define debg cout << "OK\n"
 
const ld PI = 3.1415926535;
const int N = 1e6+10;
const int M = 7e6 + 1;
int mod = 1e9+7;
const int infi = INT_MAX;
const ll infl = LLONG_MAX;
const int P = 2;
 
int mult(int a, int b) {
    return a * 1LL * b % mod;
}
 
int sum(int a, int b) { 
    if (a + b < 0)
        return a + b + mod;
    if (a + b >= mod)
        return a + b - mod;
    return a + b;
}
 
ll binpow(ll a, ll n) {
    if (n == 0)
        return 1;
    if (n % 2 == 1) {
        return binpow(a, n - 1) * a % mod;
    } else {
        ll b = binpow(a, n / 2);
        return b * b % mod;
    }
}

struct segtree{
    vector<int> t, lz;

    segtree(){

    }

    segtree(int n){
        t.assign(4 * n + 2, 0);
        lz.assign(4 * n + 2, 0);
    }

    void push(int v, int tl, int tr){
        if(tl == tr || !lz[v])
            return;
        lz[2 * v] += lz[v];
        lz[2 * v + 1] += lz[v];
        t[2 * v] += lz[v];
        t[2 * v + 1] += lz[v];
        lz[v] = 0;
    }

    int get(int v, int tl, int tr, int l, int r){
        push(v, tl, tr);
        return t[v];
    }

    void add(int v, int tl, int tr, int l, int r, int x){
        if(l > r)
            return;
        push(v, tl, tr);
        if(tl > r || l > tr)
            return;
        if(l <= tl && tr <= r){
            t[v] += x;
            lz[v] += x;
            return;
        }   
        int tm = (tl + tr) / 2;
        add(2 * v, tl, tm, l, r, x);
        add(2 * v + 1, tm + 1, tr, l, r, x);
        t[v] = min(t[2 * v], t[2 * v + 1]);
    }
    void add(int v, int tl, int tr, int i, int x){
        push(v, tl, tr);
        if(tl == tr){
            t[v] += x;
            return;
        }
        int tm = (tl + tr) / 2;
        if(i <= tm)
            add(2 * v, tl, tm, i, x);
        else
            add(2 * v + 1, tm + 1, tr, i, x);
        t[v] = min(t[2 * v], t[2 * v + 1]);
    }
};

struct answer{
    int n, m;
    vector<int> c;
    vector<vector<int>> ps;
    segtree tr;
    
    answer(){

    }

    answer(int _n, int _m, vector<int> _c){ 
        n = _n;
        m = _m;
        c = _c;
        ps.assign(m + 1, vector<int>());
        for(int i = 1; i <= n; i++){
            ps[c[i]].pb(i);
        }
    }

    void prec(){
        tr = segtree(m);
        for(int i = 1; i <= m; i++){
            tr.add(1, 1, m, i, n - sz(ps[i]));
        }
    }

    int getans(int cl){
        tr.add(1, 1, m, cl, 1e9);
        for(int i : ps[cl]){
            int d;
            if(i % 2)
                d = 1;
            else 
                d = -1;
            if(c[i + d] == cl)
                continue;
            tr.add(1, 1, m, c[i + d], 1);
        }
        int ret = tr.get(1, 1, m, 1, m) - sz(ps[cl]);
        tr.add(1, 1, m, cl, -1e9);
        for(int i : ps[cl]){
            int d;
            if(i % 2)
                d = 1;
            else 
                d = -1;
            if(c[i + d] == cl)
                continue;
            tr.add(1, 1, m, c[i + d], -1);
        }
        return ret;
    }    
};

int n, m, c[N], ans[N], blya[N];
 
void solve(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        blya[c[i]]++;
    }
    for(int i = 1; i <= m; i++)
        ans[i] = infi;
    int sm = 0;
    vector<int> fc(n - (n % 2) + 1);
    for(int i = 1; i < sz(fc); i++)
        fc[i] = c[i];
    answer fa = answer(n - (n % 2), m, fc);
    fa.prec();
    if(n % 2){
        fa.tr.add(1, 1, m, 1, c[n] - 1, 1);
        fa.tr.add(1, 1, m, c[n] + 1, m, 1);
    }
    answer sa;
    vector<int> sc;
    if(n % 2 == 1){
        sc.resize(n);
        for(int i = 2; i <= n; i++)
            sc[i - 1] = c[i];
        sa = answer(n - 1, m, sc);
        sa.prec();
        sa.tr.add(1, 1, m, 1, c[1] - 1, 1);
        sa.tr.add(1, 1, m, c[1] + 1, m, 1);
    }else{
        sc.resize(n - 1);
        for(int i = 2; i < n; i++)
            sc[i - 1] = c[i];
        sa = answer(n - 2, m, sc);
        sa.prec();
        sa.tr.add(1, 1, m, 1, c[1] - 1, 1);
        sa.tr.add(1, 1, m, c[1] + 1, m, 1);
        sa.tr.add(1, 1, m, 1, c[n] - 1, 1);
        sa.tr.add(1, 1, m, c[n] + 1, m, 1);
    }
    for(int i = 1; i <= m; i++){
        int ans1 = fa.getans(i);
        if(i == c[n] && (n % 2 == 1)){
            ans1--;
        }
        int ans2 = sa.getans(i);
        if(n % 2){
            if(c[1] == i){
                ans2--;
            }
        }else{
            if(c[1] == i){
                ans2--;
            }
            if(c[n] == i){
                ans2--;
            }
        }
        cout << min(min(ans1, ans2), n - blya[i]) << '\n';
    }
}
 
signed main() {
    mispertion;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Compilation message (stderr)

rope.cpp: In function 'void solve()':
rope.cpp:178:9: warning: unused variable 'sm' [-Wunused-variable]
  178 |     int sm = 0;
      |         ^~

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