Submission #974300

#	Time	Username	Problem	Language	Result	Execution time	Memory
974300		Pannda	Sequence (APIO23_sequence)	C++17	28 / 100	2050 ms	102228 KiB

sequence

#include "sequence.h"

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

struct LazySegmentTree {
    int n;
    vector<int> mx;
    vector<int> lazy;

    LazySegmentTree(vector<int> a) : n(a.size()), mx(4 * n), lazy(4 * n, 0) {
        auto build = [&](auto self, int idx, int l, int r) -> void {
            if (l + 1 == r) {
                mx[idx] = a[l];
            } else {
                int m = (l + r) >> 1;
                self(self, 2 * idx + 1, l, m);
                self(self, 2 * idx + 2, m, r);
                mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
            }
        };
        build(build, 0, 0, n);
    }

    void apply(int idx, int delta) {
        mx[idx] += delta;
        lazy[idx] += delta;
    }

    void down(int idx) {
        apply(2 * idx + 1, lazy[idx]);
        apply(2 * idx + 2, lazy[idx]);
        lazy[idx] = 0;
    }

    void rangeApply(int ql, int qr, int delta) {
        auto dfs = [&](auto self, int idx, int l, int r) -> void {
            if (r <= ql || qr <= l) return;
            if (ql <= l && r <= qr) return apply(idx, delta);
            down(idx);
            int m = (l + r) >> 1;
            self(self, 2 * idx + 1, l, m);
            self(self, 2 * idx + 2, m, r);
            mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
        };
        dfs(dfs, 0, 0, n);
    }

    int rangeQuery(int ql, int qr) {
        auto dfs = [&](auto self, int idx, int l, int r) -> int {
            if (r <= ql || qr <= l) return -1e9;
            if (ql <= l && r <= qr) return mx[idx];
            down(idx);
            int m = (l + r) >> 1;
            return max(self(self, 2 * idx + 1, l, m), self(self, 2 * idx + 2, m, r));
        };
        return dfs(dfs, 0, 0, n);
    }
};

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int i, int delta) {
        for (i++; i <= n; i += i & -i) {
            bit[i] += delta;
        }
    }

    int sum(int i) {
        int res = 0;
        for (; i > 0; i -= i & -i) {
            res += bit[i];
        }
        return res;
    }

    int sum(int ql, int qr) {
        return sum(qr) - sum(ql);
    }
};

int sequence(int n, vector<int> a) {
    vector<vector<int>> mp(n);
    for (int i = 0; i < n; i++) {
        a[i]--;
        mp[a[i]].push_back(i);
    }

    auto ok = [&](int x) -> bool {
        Fenwick fen(n);
        vector<int> lr(n + 1), rl(n + 1);
        for (int i = 0; i <= n; i++) {
            lr[i] = {-i};
            rl[i] = {i - n};
        }
        LazySegmentTree seg_le_lr(lr);
        LazySegmentTree seg_le_rl(rl);
        LazySegmentTree seg_ge_lr(lr);
        LazySegmentTree seg_ge_rl(rl);
        for (int i = 0; i < n; i++) {
            seg_ge_lr.rangeApply(i + 1, n + 1, +2);
            seg_ge_rl.rangeApply(0, i + 1, +2);
        }

        for (int med = 0; med < n; med++) {
            for (int i : mp[med]) {
                fen.add(i, +1);
                seg_le_lr.rangeApply(i + 1, n + 1, +2);
                seg_le_rl.rangeApply(0, i + 1, +2);
            }
            for (int ii = 0; ii + x <= mp[med].size(); ii++) {
                int l = mp[med][ii];
                int r = mp[med][ii + x - 1] + 1;
                int lem = fen.sum(l, r);
                int gem = (r - l) - lem + x;
                if (2 * lem >= r - l && 2 * gem >= r - l) return true;
                if (2 * lem < r - l) {
                    int val = 2 * lem - r + l; // < 0
                    int up = seg_le_lr.rangeQuery(r, n + 1) - seg_le_lr.rangeQuery(r, r + 1) + seg_le_rl.rangeQuery(0, l + 1) - seg_le_rl.rangeQuery(l, l + 1);
                    if (val + up >= 0) return true;
                } else {
                    int val = 2 * gem - r + l; // < 0
                    int up = seg_ge_lr.rangeQuery(r, n + 1) - seg_ge_lr.rangeQuery(r, r + 1) + seg_ge_rl.rangeQuery(0, l + 1) - seg_ge_rl.rangeQuery(l, l + 1);
                    if (val + up >= 0) return true;
                }
            }
            for (int i : mp[med]) {
                seg_ge_lr.rangeApply(i + 1, n + 1, -2);
                seg_ge_rl.rangeApply(0, i + 1, -2);
            }
        }
        return false;
    };

    int ans = [&]() -> int {
        int l = 1, r = n;
        while (l < r) {
            int m = (l + r + 1) >> 1;
            if (ok(m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        return l;
    }();

    return ans;
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:115:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |             for (int ii = 0; ii + x <= mp[med].size(); ii++) {
      |                              ~~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18