Submission #954527

#	Time	Username	Problem	Language	Result	Execution time	Memory
954527		GrandTiger1729	Sličnost (COI23_slicnost)	C++17	17 / 100	525 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() = default;
    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();
    }
    ~SegTree()
    {
        if (l == r - 1)
        {
            return;
        }
        delete lc;
        delete rc;
    }
    Data val()
    {
        return Data(val_.maxn + lz, val_.cnt);
    }
    void push()
    {
        if (lz != 0)
        {
            lc = new SegTree(*lc);
            rc = new SegTree(*rc);
            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 = new SegTree(*lc);
            lc->add(ll, rr, u);
        }
        if (mid < rr)
        {
            rc = new SegTree(*rc);
            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]--;
    }
    map<long long, long long> mp;
    auto get_ans = [&]() -> Data
    {
        while (mp.size() && (--mp.end())->second == 0)
        {
            mp.erase(--mp.end());
        }
        auto x = --mp.end();
        return Data(x->first, x->second);
    };
    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);
    }
    vector<Data> res(n + 1);
    vector<SegTree *> st(n + 1);
    for (int t = 0; t <= n; t++)
    {
        st[t] = (t == 0) ? new SegTree(0, n) : new SegTree(*st[t - 1]);
        for (int id : add[t])
        {
            int l = max(0, bb[id] - (K - 1)) + (K - 1), r = min(n, bb[id] + K);
            st[t]->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[t]->add(l, r, -1);
        }
        res[t] = st[t]->query(K - 1, n);
        mp[res[t].maxn] += res[t].cnt;
    }
    auto ans = get_ans();
    cout << ans.maxn << ' ' << ans.cnt << '\n';
    while (q--)
    {
        int i;
        cin >> i;
        i--;
        int x = a[i], y = a[i + 1];
        {
            int l = max(0, bb[x] - (K - 1)) + (K - 1), r = min(n, bb[x] + K);
            if (max(0, aa[x] - (K - 1)) + (K - 1) != max(0, aa[x] + 1 - (K - 1)) + (K - 1))
            {
                int t = max(0, aa[x] - (K - 1)) + (K - 1);
                st[t]->add(l, r, -1);
                mp[res[t].maxn] -= res[t].cnt;
                res[t] = st[t]->query(K - 1, n);
                mp[res[t].maxn] -= res[t].cnt;
            }
            if (min(n, aa[x] + K) != min(n, aa[x] + 1 + K))
            {
                int t = min(n, aa[x] + K);
                st[t]->add(l, r, 1);
                mp[res[t].maxn] -= res[t].cnt;
                res[t] = st[t]->query(K - 1, n);
                mp[res[t].maxn] -= res[t].cnt;
            }
        }
        {
            int l = max(0, bb[y] - (K - 1)) + (K - 1), r = min(n, bb[y] + K);
            if (max(0, aa[y] - (K - 1)) + (K - 1) != max(0, aa[y] - 1 - (K - 1)) + (K - 1))
            {
                int t = max(0, aa[y] - 1 - (K - 1)) + (K - 1);
                st[t]->add(l, r, 1);
                mp[res[t].maxn] -= res[t].cnt;
                res[t] = st[t]->query(K - 1, n);
                mp[res[t].maxn] -= res[t].cnt;
            }
            if (min(n, aa[y] + K) != min(n, aa[y] - 1 + K))
            {
                int t = min(n, aa[y] - 1 + K);
                st[t]->add(l, r, -1);
                mp[res[t].maxn] -= res[t].cnt;
                res[t] = st[t]->query(K - 1, n);
                mp[res[t].maxn] -= res[t].cnt;
            }
        }
        aa[x]++, aa[y]--;
        swap(a[i], a[i + 1]);
        ans = get_ans();
        cout << ans.maxn << ' ' << ans.cnt << '\n';
    }
    return 0;
}

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