Submission #1131791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131791		Hectonit	Sličnost (COI23_slicnost)	C++20	67 / 100	1726 ms	589824 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SegTree {
    vector<int> ls, rs, cmx, mx, tp, cpr;

    int nw(int lb, int rb) {
        ls.push_back(-1);
        rs.push_back(-1);
        cmx.push_back(rb - lb);
        mx.push_back(0);
        tp.push_back(0);
        cpr.push_back(-1);
        return (int)ls.size() - 1;
    }

    SegTree(int n) {
        nw(0, n);
    }

    void apply(int i, int tpn) {
        mx[i] += tpn;
        tp[i] += tpn;
    }

    int copy(int i) {
        int ni = ls.size();
        ls.push_back(-1);
        rs.push_back(-1);
        cmx.push_back(cmx[i]);
        mx.push_back(mx[i]);
        tp.push_back(tp[i]);
        cpr.push_back(i);
        if (ls[cpr[ni]] == -1) {
            cpr[ni] = cpr[cpr[ni]];
        }
        return ni;
    }

    void push(int i, int l, int r) {
        if (ls[i] == -1) {
            if (cpr[i] != -1) {
                int cprn = cpr[i];
                ls[i] = copy(ls[cprn]);
                rs[i] = copy(rs[cprn]);
            } else {
                int m = (l + r) / 2;
                ls[i] = nw(l, m);
                rs[i] = nw(m, r);
            }
        }
        if (tp[i]) {
            apply(ls[i], tp[i]);
            apply(rs[i], tp[i]);
            tp[i] = 0;
        }
    }

    int upd(bool init, int i, int l, int r, int ql, int qr, int x) {
        if (init) {
            i = copy(i);
        }
        if (l >= qr || ql >= r) return i;
        if (ql <= l && r <= qr) {
            mx[i] += x;
            tp[i] += x;
            return i;
        }
        push(i, l, r);
        int m = (l + r) / 2;
        upd(false, ls[i], l, m, ql, qr, x);
        upd(false, rs[i], m, r, ql, qr, x);
        mx[i] = max(mx[ls[i]], mx[rs[i]]);
        cmx[i] = 0;
        if (mx[ls[i]] == mx[i]) {
            cmx[i] += cmx[ls[i]];
        }
        if (mx[rs[i]] == mx[i]) {
            cmx[i] += cmx[rs[i]];
        }
        return i;
    }
};

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    vector<int> p(n), q(n);
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    vector<int> pos(n);
    for (int i = 0; i < n; i++) {
        cin >> q[i];
        q[i]--;
        pos[q[i]] = i;
    }
    SegTree t(n);
    int vnow = 0;
    for (int i = 0; i < k - 1; i++) {
        vnow = t.upd(true, vnow, 0, n, max(0, pos[p[i]] - k + 1), min(pos[p[i]], n - k) + 1, 1);
    }
    map<ll, ll> mp;
    vector<int> verses(n - k + 1);
    for (int i = 0; i < n - k + 1; i++) {
        vnow = t.upd(true, vnow, 0, n, max(0, pos[p[i + k - 1]] - k + 1), min(pos[p[i + k - 1]], n - k) + 1, 1);
        verses[i] = vnow;
        mp[t.mx[vnow]] += t.cmx[vnow];
        vnow = t.upd(true, vnow, 0, n, max(0, pos[p[i]] - k + 1), min(pos[p[i]], n - k) + 1, -1);
    }
    auto [ans, cans] = *mp.rbegin();
    cout << ans << ' ' << cans << '\n';
    for (int i = 0; i < m; i++) {
        int j;
        cin >> j;
        j--;
        int p1 = p[j], p2 = p[j + 1];
        if (j - k + 1 >= 0) {
            int s1 = j - k + 1;
            vnow = verses[s1];
            mp[t.mx[vnow]] -= t.cmx[vnow];
            if (mp[t.mx[vnow]] == 0) {
                mp.erase(t.mx[vnow]);
            }
            vnow = t.upd(true, vnow, 0, n, max(0, pos[p1] - k + 1), min(pos[p1], n - k) + 1, -1);
            vnow = t.upd(true, vnow, 0, n, max(0, pos[p2] - k + 1), min(pos[p2], n - k) + 1, 1);
            mp[t.mx[vnow]] += t.cmx[vnow];
            verses[s1] = vnow;
        }
        if (j + 1 < n - k + 1) {
            int s2 = j + 1;
            vnow = verses[s2];
            mp[t.mx[vnow]] -= t.cmx[vnow];
            if (mp[t.mx[vnow]] == 0) {
                mp.erase(t.mx[vnow]);
            }
            vnow = t.upd(true, vnow, 0, n, max(0, pos[p1] - k + 1), min(pos[p1], n - k) + 1, 1);
            vnow = t.upd(true, vnow, 0, n, max(0, pos[p2] - k + 1), min(pos[p2], n - k) + 1, -1);
            mp[t.mx[vnow]] += t.cmx[vnow];
            verses[s2] = vnow;
        }
        auto [ans, cans] = *mp.rbegin();
        cout << ans << ' ' << cans << '\n';
        swap(p[j], p[j + 1]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 33 / 33
• Subtask 4: 7 / 7
• Subtask 5: 10 / 10
• Subtask 6: 0 / 33