Submission #1131694

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

Main

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct SegTree {
    struct Node {
        ll ls = -1, rs = -1, cmx = 0, mx = 0, tp = 0, cpr = -1;

        Node(int lb, int rb) {
            cmx = rb - lb;
        }
    };

    vector<Node> t;

    SegTree(int n) {
        t.push_back(Node(0, n));
    }

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

    void push(int i, int l, int r) {
        if (t[i].ls == -1) {
            while (t[i].cpr != -1 && t[t[i].cpr].ls == -1) {
                t[i].cpr = t[t[i].cpr].cpr;
            }
            if (t[i].cpr != -1) {
                int cpr = t[i].cpr;
                t[i].ls = t.size();
                t.push_back(t[t[cpr].ls]);
                t.back().ls = -1;
                t.back().rs = -1;
                t.back().cpr = t[cpr].ls;
                t[i].rs = t.size();
                t.push_back(t[t[cpr].rs]);
                t.back().ls = -1;
                t.back().rs = -1;
                t.back().cpr = t[cpr].rs;
            } else {
                int m = (l + r) / 2;
                t[i].ls = t.size();
                t.push_back(Node(l, m));
                t[i].rs = t.size();
                t.push_back(Node(m, r));
            }
        }
        if (t[i].tp) {
            apply(t[i].ls, t[i].tp);
            apply(t[i].rs, t[i].tp);
            t[i].tp = 0;
        }
    }

    int upd(bool init, int i, int l, int r, int ql, int qr, int x) {
        if (init) {
            //cout << ql << ' ' << qr << ' ' << x << '\n';
            int ni = t.size();
            t.push_back(t[i]);
            t[ni].ls = -1;
            t[ni].rs = -1;
            t[ni].cpr = i;
            i = ni;
        }
        if (l >= qr || ql >= r) return i;
        if (ql <= l && r <= qr) {
            t[i].mx += x;
            t[i].tp += x;
            return i;
        }
        push(i, l, r);
        int m = (l + r) / 2;
        upd(false, t[i].ls, l, m, ql, qr, x);
        upd(false, t[i].rs, m, r, ql, qr, x);
        t[i].mx = max(t[t[i].ls].mx, t[t[i].rs].mx);
        t[i].cmx = 0;
        if (t[t[i].ls].mx == t[i].mx) {
            t[i].cmx += t[t[i].ls].cmx;
        }
        if (t[t[i].rs].mx == t[i].mx) {
            t[i].cmx += t[t[i].rs].cmx;
        }
        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.t[vnow].mx] += t.t[vnow].cmx;
        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--;
        auto [ans, cans] = *mp.rbegin();
        cout << ans << ' ' << cans << '\n';
    }
}

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: 0 / 33
• Subtask 4: 0 / 7
• Subtask 5: 0 / 10
• Subtask 6: 0 / 33