Submission #1180371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180371		patgra	Rope (JOI17_rope)	C++20	55 / 100	2597 ms	146316 KiB

rope

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 1;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

struct hsh {
    ll operator() (pair<int, int> x) const {
        ll a = x.first, b = x.second;
        return (a << 32) | b;
    }
};

int n, m;
vector<int> iniCol;
vector<int> ans;
unordered_map<pair<int, int>, int, hsh> ileTakich;
vector<int> ilePojedynczych, ilePodwojnych;
map<pair<int, int>, int> ileTakich2;
vector<int> ilePojedynczych2, ilePodwojnych2;
vector<set<int>> skim;
vector<pair<int, int>> t;
int tb;

void checkCols(int c1, int c2) {
    if(c1 > c2) swap(c1, c2);
    int ileWsumie = n / 2;
    auto ilePoj = ilePojedynczych[c1] + (c1 == c2 ? 0 : ilePojedynczych[c2] - (ileTakich.contains(pair{c1, c2}) ? ileTakich[pair{c1, c2}] : 0));
    auto ilePod = ilePodwojnych[c1] + (c1 == c2 ? 0 : ilePodwojnych[c2]);
    auto cost1 = (ileWsumie - ilePod) * 2 - ilePoj;
    if(n % 2 == 1) cost1 += iniCol.back() != c1 && iniCol.back() != c2;

    if(n % 2 == 0) ileWsumie--;
    ilePoj = ilePojedynczych2[c1] + (c1 == c2 ? 0 : ilePojedynczych2[c2] - (ileTakich2.contains(pair{c1, c2}) ? ileTakich2[pair{c1, c2}] : 0));
    ilePod = ilePodwojnych2[c1] + (c1 == c2 ? 0 : ilePodwojnych2[c2]);
    auto cost2 = (ileWsumie - ilePod) * 2 - ilePoj;
    cost2 += iniCol[0] != c1 && iniCol[0] != c2;
    if(n % 2 == 0) cost2 += iniCol.back() != c1 && iniCol.back() != c2;

    auto cost = min(cost1, cost2);
    ans[c1] = min(ans[c1], cost);
    ans[c2] = min(ans[c2], cost);
}

void tSet(int i, int x) {
    i += tb;
    t[i].first = x;
    while(i > 1) i /= 2, t[i] = max(t[2 * i], t[2 * i + 1]);
}
pair<int, int> tQ(int l, int r) {
    l += tb;
    r += tb;
    auto ret = max(t[l], t[r]);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ret = max(ret, t[l + 1]);
        if(r % 2 == 1) ret = max(ret, t[r - 1]);
        l /= 2; r /= 2;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> m;
    iniCol.resize(n);
    ans.resize(m + 1, 1e9);
    ilePojedynczych.resize(m + 1, 0), ilePodwojnych.resize(m + 1, 0);
    ilePojedynczych2.resize(m + 1, 0), ilePodwojnych2.resize(m + 1, 0);
    skim.resize(m + 1);
    tb = 1 << (32 - __builtin_clz(max(1, m - 1)));
    t.resize(2 * tb);
    rep(i, 0, n) cin >> iniCol[i];
    rep(i, 0, n - 1) {
        auto c1 = iniCol[i], c2 = iniCol[i + 1];
        skim[c1].insert(c2), skim[c2].insert(c1);
        if(i % 2 == 0) {
            if(c1 == c2) ilePodwojnych[c1]++;
            else ilePojedynczych[c1]++, ilePojedynczych[c2]++, ileTakich[pair{min(c1, c2), max(c1, c2)}]++;
        }
        else {
            if(c1 == c2) ilePodwojnych2[c1]++;
            else ilePojedynczych2[c1]++, ilePojedynczych2[c2]++, ileTakich2[pair{min(c1, c2), max(c1, c2)}]++;
        } 
    }

    rep(i, 0, n - 1) checkCols(iniCol[i], iniCol[i + 1]);
    rep(i, 1, m + 1) checkCols(i, i);

    rep(i, 0, tb) t[i + tb] = {-1, i};
    repD(i, tb - 1, 0) t[i] = max(t[2 * i], t[2 * i + 1]);
    rep(i, 1, m + 1) tSet(i - 1, ilePodwojnych[i] * 2 + ilePojedynczych[i]);
    rep(i, 1, m + 1) {
        pair<int, int> maxx = {-1, -1};
        skim[i].insert(i);
        auto prv = 1;
        repIn(j, skim[i]) {
            if(j > prv) maxx = max(maxx, tQ(prv - 1, j - 2));
            prv = j + 1;
        }
        if(prv <= m) maxx = max(maxx, tQ(prv - 1, m - 1));
        checkCols(i, maxx.second + 1);
    }

    rep(i, 0, tb) t[i + tb] = {-1, i};
    repD(i, tb - 1, 0) t[i] = max(t[2 * i], t[2 * i + 1]);
    rep(i, 1, m + 1) tSet(i - 1, ilePodwojnych2[i] * 2 + ilePojedynczych2[i]);
    rep(i, 1, m + 1) {
        pair<int, int> maxx = {-1, -1};
        auto prv = 1;
        repIn(j, skim[i]) {
            if(j > prv) maxx = max(maxx, tQ(prv - 1, j - 2));
            prv = j + 1;
        }
        if(prv <= m) maxx = max(maxx, tQ(prv - 1, m - 1));
        checkCols(i, maxx.second + 1);
    }

    rep(i, 0, m) cout << ans[i + 1] << '\n';
}

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