oj.uz

Submission #954507

# Submission time Handle Problem Language Result Execution time Memory
954507 2024-03-28T05:25:09 Z GrandTiger1729 Sličnost (COI23_slicnost) C++17
0 / 100
 1 ms 360 KB 
#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);
    }
    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]--;
    }
    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);
    }
    // long long ans = 0, cnt = 0;
    Data ans(-INF, 0);
    // vector<long long> dd(n);
    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);
            // for (int i = l; i < r; i++)
            // {
            //     dd[i]++;
            // }
            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);
            // for (int i = l; i < r; i++)
            // {
            //     dd[i]--;
            // }
            st.add(l, r, -1);
        }
        // long long res = 0, cc = 0;
        // for (int i = K - 1; i < n; i++)
        // {
        //     if (res < dd[i])
        //     {
        //         res = dd[i];
        //         cc = 1;
        //     }
        //     else if (res == dd[i])
        //     {
        //         cc++;
        //     }
        // }
        // if (res > ans)
        // {
        //     ans = res;
        //     cnt = cc;
        // }
        // else if (res == ans)
        // {
        //     cnt += cc;
        // }
        Data res = st.query(K - 1, n);
        ans = merge(ans, res);
    }
    cout << ans.maxn << ' ' << ans.cnt << '\n';
    return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 360 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Incorrect 0 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -