oj.uz

Submission #954527

# Submission time Handle Problem Language Result Execution time Memory
954527 2024-03-28T06:07:26 Z GrandTiger1729 Sličnost (COI23_slicnost) C++17
17 / 100
 525 ms 524288 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() = 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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Correct 9 ms 9572 KB Output is correct
17 Correct 11 ms 10272 KB Output is correct
18 Correct 8 ms 9572 KB Output is correct
19 Correct 21 ms 24576 KB Output is correct
20 Correct 23 ms 21432 KB Output is correct
21 Correct 15 ms 18780 KB Output is correct
22 Correct 11 ms 11356 KB Output is correct
23 Correct 27 ms 20564 KB Output is correct
24 Correct 16 ms 17500 KB Output is correct
25 Correct 29 ms 26460 KB Output is correct
26 Correct 25 ms 29108 KB Output is correct
27 Correct 24 ms 27212 KB Output is correct
28 Correct 21 ms 25692 KB Output is correct
29 Correct 18 ms 22244 KB Output is correct
30 Correct 7 ms 8028 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Correct 9 ms 9572 KB Output is correct
17 Correct 11 ms 10272 KB Output is correct
18 Correct 8 ms 9572 KB Output is correct
19 Correct 21 ms 24576 KB Output is correct
20 Correct 23 ms 21432 KB Output is correct
21 Correct 15 ms 18780 KB Output is correct
22 Correct 11 ms 11356 KB Output is correct
23 Correct 27 ms 20564 KB Output is correct
24 Correct 16 ms 17500 KB Output is correct
25 Correct 29 ms 26460 KB Output is correct
26 Correct 25 ms 29108 KB Output is correct
27 Correct 24 ms 27212 KB Output is correct
28 Correct 21 ms 25692 KB Output is correct
29 Correct 18 ms 22244 KB Output is correct
30 Correct 7 ms 8028 KB Output is correct
31 Correct 319 ms 238164 KB Output is correct
32 Correct 320 ms 252436 KB Output is correct
33 Correct 174 ms 235580 KB Output is correct
34 Runtime error 525 ms 524288 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Incorrect 1 ms 604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Correct 9 ms 9572 KB Output is correct
17 Correct 11 ms 10272 KB Output is correct
18 Correct 8 ms 9572 KB Output is correct
19 Correct 21 ms 24576 KB Output is correct
20 Correct 23 ms 21432 KB Output is correct
21 Correct 15 ms 18780 KB Output is correct
22 Correct 11 ms 11356 KB Output is correct
23 Correct 27 ms 20564 KB Output is correct
24 Correct 16 ms 17500 KB Output is correct
25 Correct 29 ms 26460 KB Output is correct
26 Correct 25 ms 29108 KB Output is correct
27 Correct 24 ms 27212 KB Output is correct
28 Correct 21 ms 25692 KB Output is correct
29 Correct 18 ms 22244 KB Output is correct
30 Correct 7 ms 8028 KB Output is correct
31 Incorrect 1 ms 604 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #6
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 352 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 0 ms 356 KB Output is correct
16 Correct 9 ms 9572 KB Output is correct
17 Correct 11 ms 10272 KB Output is correct
18 Correct 8 ms 9572 KB Output is correct
19 Correct 21 ms 24576 KB Output is correct
20 Correct 23 ms 21432 KB Output is correct
21 Correct 15 ms 18780 KB Output is correct
22 Correct 11 ms 11356 KB Output is correct
23 Correct 27 ms 20564 KB Output is correct
24 Correct 16 ms 17500 KB Output is correct
25 Correct 29 ms 26460 KB Output is correct
26 Correct 25 ms 29108 KB Output is correct
27 Correct 24 ms 27212 KB Output is correct
28 Correct 21 ms 25692 KB Output is correct
29 Correct 18 ms 22244 KB Output is correct
30 Correct 7 ms 8028 KB Output is correct
31 Correct 319 ms 238164 KB Output is correct
32 Correct 320 ms 252436 KB Output is correct
33 Correct 174 ms 235580 KB Output is correct
34 Runtime error 525 ms 524288 KB Execution killed with signal 9
35 Halted 0 ms 0 KB -