Submission #1144041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144041		Hectonit	Sličnost (COI23_slicnost)	C++20	100 / 100	657 ms	34584 KiB

Main

#ifdef DEBUG
#include <bits/stdc++_deb.h>
#else
#include <bits/stdc++.h>
#endif

using namespace std;

using ll = long long;
using ld = long double;

const int inf = 1e9 + 10;

struct SegTree {
    struct Node {
        ll mx = 0, cnt = 0, tp = 0;
    };

    Node merge(Node a, Node b) {
        Node res;
        res.mx = max(a.mx, b.mx);
        if (res.mx == a.mx) {
            res.cnt += a.cnt;
        }
        if (res.mx == b.mx) {
            res.cnt += b.cnt;
        }
        return res;
    }

    vector<Node> t;

    SegTree(int n) {
        t.resize(n * 4);
        build(0, n, 0);
    }

    void build(int l, int r, int i) {
        if (l + 1 == r) {
            t[i].cnt = 1;
            return;
        }
        int m = (l + r) / 2;
        build(l, m, i * 2 + 1);
        build(m, r, i * 2 + 2);
        t[i] = merge(t[i * 2 + 1], t[i * 2 + 2]);
    }

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

    void push(int i) {
        apply(i * 2 + 1, t[i].tp);
        apply(i * 2 + 2, t[i].tp);
        t[i].tp = 0;
    }

    void upd(int l, int r, int i, int ql, int qr, int x) {
        if (ql >= r || l >= qr) return;
        if (ql <= l && r <= qr) {
            apply(i, x);
            return;
        }
        push(i);
        int m = (l + r) / 2;
        upd(l, m, i * 2 + 1, ql, qr, x);
        upd(m, r, i * 2 + 2, ql, qr, x);
        t[i] = merge(t[i * 2 + 1], t[i * 2 + 2]);
    }

    Node get(int l, int r, int i, int ql, int qr) {
        if (ql >= r || l >= qr) return Node();
        if (ql <= l && r <= qr) {
            return t[i];
        }
        push(i);
        int m = (l + r) / 2;
        auto r1 = get(l, m, i * 2 + 1, ql, qr);
        auto r2 = get(m, r, i * 2 + 2, ql, qr);
        return merge(r1, r2);
    }
};

struct SegTreeAns {
    struct Node {
        ll mx = 0, cnt = 0;
    };

    vector<Node> t;

    SegTreeAns(int n) {
        t.resize(n * 4);
    }

    void apply(int i, ll mx, ll mxc) {
        if (t[i].mx < mx) {
            t[i].mx = mx;
            t[i].cnt = mxc;
        } else if (t[i].mx == mx) {
            t[i].cnt += mxc;
        }
    }

    void push(int i) {
        apply(i * 2 + 1, t[i].mx, t[i].cnt);
        apply(i * 2 + 2, t[i].mx, t[i].cnt);
        t[i].mx = 0;
        t[i].cnt = 0;
    }

    void upd(int l, int r, int i, int ql, int qr, ll mx, ll mxc) {
        if (ql >= r || l >= qr) return;
        if (ql <= l && r <= qr) {
            apply(i, mx, mxc);
            return;
        }
        int m = (l + r) / 2;
        push(i);
        upd(l, m, i * 2 + 1, ql, qr, mx, mxc);
        upd(m, r, i * 2 + 2, ql, qr, mx, mxc);
    }

    array<ll, 2> get(int l, int r, int i, int idx) {
        if (l + 1 == r) {
            return {t[i].mx, t[i].cnt};
        }
        int m = (l + r) / 2;
        push(i);
        if (idx < m) {
            return get(l, m, i * 2 + 1, idx);
        } else {
            return get(m, r, i * 2 + 2, idx);
        }
    }
};

void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> p1(n), p2(n);
    vector<int> pos1(n + 1), pos2(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> p1[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> p2[i];
        pos2[p2[i]] = i;
    }
    vector<vector<array<int, 4>>> upds(n + 1);
    for (int i = 0; i < n; i++) {
        int st = max(i - k + 1, 0), en = i + 1;
        int lb = max(pos2[p1[i]] - k + 1, 0), rb = pos2[p1[i]];
        upds[st].push_back({0, lb, rb, 1});
        upds[en].push_back({0, lb, rb, -1});
    }
    for (int i = 0; i < q; i++) {
        int idx;
        cin >> idx;
        idx--;
        int st1 = max(idx - k + 1, 0), en1 = idx + 1;
        int st2 = max(idx - k + 2, 0), en2 = idx + 2;
        int lb1 = max(pos2[p1[idx]] - k + 1, 0), rb1 = pos2[p1[idx]];
        int lb2 = max(pos2[p1[idx + 1]] - k + 1, 0), rb2 = pos2[p1[idx + 1]];

        if (st1 != st2) {
            upds[st1].push_back({i + 1, lb1, rb1, -1});
            upds[st1].push_back({i + 1, lb2, rb2, 1});
        }

        upds[en1].push_back({i + 1, lb2, rb2, -1});
        upds[en1].push_back({i + 1, lb1, rb1, 1});

        swap(p1[idx], p1[idx + 1]);
    }
    SegTree t(n);
    SegTreeAns ans(q + 1);
    for (int i = 0; i < n - k + 1; i++) {
        map<int, int> en;
        int cnt = 0;
        //cout << i << '\n';
        for (auto [tm, lb, rb, x] : upds[i]) {
            //cout << tm << ' ' << lb << ' ' << rb << ' ' << x << '\n';
            en[tm] = cnt;
            cnt++;
        }
        //cout << "end upd\n";
        cnt = 0;
        for (auto [tm, lb, rb, x] : upds[i]) {
            t.upd(0, n, 0, lb, rb + 1, x);
            if (en[tm] == cnt) {
                auto res = t.get(0, n, 0, 0, n - k + 1);
                ll mx = res.mx, mxc = res.cnt;
                int nxt = q + 1;
                if (cnt + 1 < (int)upds[i].size()) {
                    nxt = upds[i][cnt + 1][0];
                }
                //cout << mx << ' ' << mxc << ' ' << tm << ' ' << nxt << '\n';
                ans.upd(0, q + 1, 0, tm, nxt, mx, mxc);
            }
            cnt++;
        }
        for (auto [tm, lb, rb, x] : upds[i]) {
            if (tm != 0) {
                t.upd(0, n, 0, lb, rb + 1, -x);
            }
        }
    }
    for (int i = 0; i <= q; i++) {
        auto [mx, mxc] = ans.get(0, q + 1, 0, i);
        cout << mx << ' ' << mxc << '\n';
    }
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int t = 1;
    //cin >> t;
    for (int i = 0; i < t; i++) solve();
}

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