Submission #954508

#	Time	Username	Problem	Language	Result	Execution time	Memory
954508		GrandTiger1729	Sličnost (COI23_slicnost)	C++17	57 / 100	2035 ms	524288 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
struct Data
{
    long long maxn = 0, cnt = 0;
    Data() = default;
    Data(long long maxn_, long long cnt_) : maxn(maxn_), cnt(cnt_) {}
    inline friend Data merge(Data a, Data b)
    {
        if (a.maxn < b.maxn)
        {
            return b;
        }
        if (a.maxn > b.maxn)
        {
            return a;
        }
        return Data(a.maxn, a.cnt + b.cnt);
    }
};
struct SegTree
{
    int l, r, mid;
    SegTree *lc, *rc;
    Data val_;
    long long lz = 0;
    SegTree(int l_, int r_) : l(l_), r(r_)
    {
        mid = (l + r) / 2;
        if (l == r - 1)
        {
            val_ = Data(0, 1);
            return;
        }
        lc = new SegTree(l, mid);
        rc = new SegTree(mid, r);
        pull();
    }
    Data val()
    {
        return Data(val_.maxn + lz, val_.cnt);
    }
    void push()
    {
        if (lz != 0)
        {
            lc->lz += lz;
            rc->lz += lz;
            lz = 0;
        }
    }
    void pull()
    {
        val_ = merge(lc->val(), rc->val());
    }
    void add(int ll, int rr, long long u)
    {
        if (ll <= l && rr >= r)
        {
            lz += u;
            return;
        }
        push();
        if (ll < mid)
        {
            lc->add(ll, rr, u);
        }
        if (mid < rr)
        {
            rc->add(ll, rr, u);
        }
        pull();
    }
    Data query(int ll, int rr)
    {
        if (ll <= l && rr >= r)
        {
            return val();
        }
        push();
        Data ret(-INF, 0);
        if (ll < mid)
        {
            ret = merge(ret, lc->query(ll, rr));
        }
        if (mid < rr)
        {
            ret = merge(ret, rc->query(ll, rr));
        }
        pull();
        return ret;
    }
};

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, K, q;
    cin >> n >> K >> q;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--;
    }
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        b[i]--;
    }
    auto solve = [&]()
    {
        vector<int> aa(n), bb(n);
        for (int i = 0; i < n; i++)
        {
            aa[a[i]] = i;
            bb[b[i]] = i;
        }
        vector<vector<int>> add(n + 1), del(n + 1);
        for (int i = 0; i < n; i++)
        {
            add[max(0, aa[i] - (K - 1)) + (K - 1)].push_back(i);
            del[min(n, aa[i] + K)].push_back(i);
        }
        Data ans(-INF, 0);
        SegTree st(0, n);
        for (int t = 0; t <= n; t++)
        {
            for (int id : add[t])
            {
                int l = max(0, bb[id] - (K - 1)) + (K - 1), r = min(n, bb[id] + K);
                st.add(l, r, 1);
            }
            for (int id : del[t])
            {
                int l = max(0, bb[id] - (K - 1)) + (K - 1), r = min(n, bb[id] + K);
                st.add(l, r, -1);
            }
            Data res = st.query(K - 1, n);
            ans = merge(ans, res);
        }
        cout << ans.maxn << ' ' << ans.cnt << '\n';
    };
    solve();
    while (q--)
    {
        int i;
        cin >> i;
        i--;
        swap(a[i], a[i + 1]);
        solve();
    }
    return 0;
}

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