oj.uz

Submission #974300

# Submission time Handle Problem Language Result Execution time Memory
974300 2024-05-03T07:47:33 Z Pannda Sequence (APIO23_sequence) C++17
28 / 100
 2000 ms 102228 KB 
#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

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.0 / 11.0

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

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 22 ms 848 KB Output is correct
14 Correct 20 ms 960 KB Output is correct
15 Correct 19 ms 824 KB Output is correct
16 Correct 20 ms 772 KB Output is correct
17 Correct 19 ms 772 KB Output is correct
18 Correct 18 ms 804 KB Output is correct
19 Correct 20 ms 768 KB Output is correct
20 Correct 20 ms 1028 KB Output is correct
21 Correct 21 ms 772 KB Output is correct
22 Correct 22 ms 812 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2050 ms 96680 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 2028 ms 88824 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 102228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 22 ms 848 KB Output is correct
14 Correct 20 ms 960 KB Output is correct
15 Correct 19 ms 824 KB Output is correct
16 Correct 20 ms 772 KB Output is correct
17 Correct 19 ms 772 KB Output is correct
18 Correct 18 ms 804 KB Output is correct
19 Correct 20 ms 768 KB Output is correct
20 Correct 20 ms 1028 KB Output is correct
21 Correct 21 ms 772 KB Output is correct
22 Correct 22 ms 812 KB Output is correct
23 Execution timed out 2031 ms 16208 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 22 ms 848 KB Output is correct
14 Correct 20 ms 960 KB Output is correct
15 Correct 19 ms 824 KB Output is correct
16 Correct 20 ms 772 KB Output is correct
17 Correct 19 ms 772 KB Output is correct
18 Correct 18 ms 804 KB Output is correct
19 Correct 20 ms 768 KB Output is correct
20 Correct 20 ms 1028 KB Output is correct
21 Correct 21 ms 772 KB Output is correct
22 Correct 22 ms 812 KB Output is correct
23 Execution timed out 2050 ms 96680 KB Time limit exceeded
24 Halted 0 ms 0 KB -