Submission #749737

#	Time	Username	Problem	Language	Result	Execution time	Memory
749737		elazarkoren	Sequence (APIO23_sequence)	C++17	62 / 100	2058 ms	58212 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

const int infinity = 1e9;

struct Seg{
    int n;
    vii seg;
    vi add;
    Seg() {}
    Seg(int m) {
        for (n = 1; n < m; n <<= 1);
        seg.resize(2 * n);
        add.resize(2 * n);
    }
    inline void pull(int i) {
        seg[i].x = min(seg[i << 1].x, seg[i << 1 | 1].x);
        seg[i].y = max(seg[i << 1].y, seg[i << 1 | 1].y);
    }
    inline void push(int i) {
        add[i << 1] += add[i];
        seg[i << 1].x += add[i], seg[i << 1].y += add[i];
        add[i << 1 | 1] += add[i];
        seg[i << 1 | 1].x += add[i], seg[i << 1 | 1].y += add[i];
        add[i] = 0;
    }
    void update(int a, int b, int x, int ind, int l, int r) {
        if (a <= l && r <= b) {
            add[ind] += x;
            seg[ind].x += x, seg[ind].y += x;
            return;
        }
        if (r <= a || b <= l) return;
        push(ind);
        update(a, b, x, ind << 1, l, (l + r) >> 1);
        update(a, b, x, ind << 1 | 1, (l + r) >> 1, r);
        pull(ind);
    }
    inline void update(int a, int b, int x) {
        update(a, b, x, 1, 0, n);
    }
    pii query(int a, int b, int ind, int l, int r) {
        if (a <= l && r <= b) return seg[ind];
        if (r <= a || b <= l) return {infinity, -infinity};
        push(ind);
        pii p1 = query(a, b, ind << 1, l, (l + r) >> 1);
        pii p2 = query(a, b, ind << 1 | 1, (l + r) >> 1, r);
        return {min(p1.x, p2.x), max(p1.y, p2.y)};
    }
    inline pii query(int a, int b) {
        return query(a, b, 1, 0, n);
    }
};

int sequence(int n, vi a) {
    vi vals;
    for (int x : a) vals.push_back(x);
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int i = 0; i < n; i++) {
        a[i] = lower_bound(all(vals), a[i]) - vals.begin() + 1;
    }
    int siz = vals.size();
    vvi pos(siz + 1);
    Seg seg_minus(n + 1), seg_plus(n + 1);
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i + 1);
        seg_minus.update(i + 1, n + 1, 1);
        seg_plus.update(i + 1, n + 1, 1);
    }
    int ans = 1;
    for (int i = 1; i <= siz; i++) {
        for (int j : pos[i - 1]) {
            seg_plus.update(j, n + 1, -2);
        }
        for (int j : pos[i]) {
            seg_minus.update(j, n + 1, -2);
        }
        int sz = pos[i].size();
        vii minus_before(sz);
        vii minus_after(sz);
        vii plus_before(sz);
        vii plus_after(sz);
        for (int k = 0; k < sz; k++) {
            int j = pos[i][k];
            minus_before[k] = seg_minus.query(0, j);
            minus_after[k] = seg_minus.query(j, n + 1);
            plus_before[k] = seg_plus.query(0, j);
            plus_after[k] = seg_plus.query(j, n + 1);
        }
        int begin = ans + 1, end = sz + 1, mid;
        while (begin < end) {
            mid = (begin + end) >> 1;
            bool good = false;
            for (int ind1 = 0, ind2 = mid - 1; ind2 < pos[i].size(); ind1++, ind2++) {
                int l1 = minus_before[ind1].x, r1 = minus_before[ind1].y;
                int l2 = minus_after[ind2].x, r2 = minus_after[ind2].y;
                if (!(r1 < l2 || r2 < l1)) {
                    good = true;
                    break;
                }
                if (r2 < l1) {
                    int d = r2 - l1;
                    if (d + 2 * mid >= 0) {
                        good = true;
                        break;
                    }
                }
                l1 = plus_before[ind1].x, r1 = plus_before[ind1].y;
                l2 = plus_after[ind2].x, r2 = plus_after[ind2].y;
                if (!(r1 < l2 || r2 < l1)) {
                    good = true;
                    break;
                }
                if (r1 < l2) {
                    int d = l2 - r1;
                    if (d - 2 * mid <= 0) {
                        good = true;
                        break;
                    }
                }
            }
            if (good) begin = mid + 1;
            else end = mid;
        }
        chkmax(ans, begin - 1);
    }
    return ans;
}
/*
4
3 1 2 2
 */

/*
8
1 1 3 3 2 4 1 1
 */

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, vi)':
sequence.cpp:106:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |             for (int ind1 = 0, ind2 = mid - 1; ind2 < pos[i].size(); ind1++, ind2++) {
      |                                                ~~~~~^~~~~~~~~~~~~~~

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