Submission #755083

#	Time	Username	Problem	Language	Result	Execution time	Memory
755083		IloveN	Sequence (APIO23_sequence)	C++17	82 / 100	2001 ms	50008 KiB

sequence

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(), vr.end()

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;

const int N = 5e5 + 10;

struct segment_tree_max
{
    int it[N * 4], lazy[N * 4], n, u, v, x;

	int combine(int obj1, int obj2) { return max(obj1, obj2);}

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = 0;
            lazy[id] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
        lazy[id] = 0;
    }

    void init(int len)
    {
        n = len;
        build(1, 1, n);
    }

    void apply(int id, int val)
    {
        it[id] += val;
        lazy[id] += val;
    }

    void push(int id)
    {
        apply(id << 1, lazy[id]);
        apply((id << 1) | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            apply(id, x);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        update(id << 1, l, mid);
        update((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
    }

    int get(int id, int l, int r)
    {
        if (l > v || r < u) return -1e9;
        if (u <= l && r <= v) return it[id];
        int mid = (l + r) >> 1;
        push(id);
        return combine(get(id << 1, l, mid), get((id << 1) | 1, mid + 1, r));
    }

    int lw(int id, int l, int r)
    {
        if (l > v || r < u || it[id] < x) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        push(id);
        int tmp = lw(id << 1, l, mid);
        if (tmp != -1) return tmp;
        return lw((id << 1) | 1, mid + 1, r);
    }

    void Update(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        update(1, 1, n);
    }

    int Get(int l, int r)
    {
        u = l;
        v = r;
        if (l > r) return 0;
        return get(1, 1, n);
    }

    int Lower_bound(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        return lw(1, 1, n);
    }
} seg_mx;

struct segment_tree_min
{
    int it[N * 4], lazy[N * 4], n, u, v, x;

	int combine(int obj1, int obj2) { return min(obj1, obj2);}

    void build(int id, int l, int r)
    {
        if (l == r)
        {
            it[id] = 0;
            lazy[id] = 0;
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
        lazy[id] = 0;
    }

    void init(int len)
    {
        n = len;
        build(1, 1, n);
    }

    void apply(int id, int val)
    {
        it[id] += val;
        lazy[id] += val;
    }

    void push(int id)
    {
        apply(id << 1, lazy[id]);
        apply((id << 1) | 1, lazy[id]);
        lazy[id] = 0;
    }

    void update(int id, int l, int r)
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v)
        {
            apply(id, x);
            return;
        }
        int mid = (l + r) >> 1;
        push(id);
        update(id << 1, l, mid);
        update((id << 1) | 1, mid + 1, r);
        it[id] = combine(it[id << 1], it[(id << 1) | 1]);
    }

    int get(int id, int l, int r)
    {
        if (l > v || r < u) return 1e9;
        if (u <= l && r <= v) return it[id];
        int mid = (l + r) >> 1;
        push(id);
        return combine(get(id << 1, l, mid), get((id << 1) | 1, mid + 1, r));
    }

    int lw(int id, int l, int r)
    {
        if (l > v || r < u || it[id] > x) return -1;
        if (l == r) return l;
        int mid = (l + r) >> 1;
        push(id);
        int tmp = lw(id << 1, l, mid);
        if (tmp != -1) return tmp;
        return lw((id << 1) | 1, mid + 1, r);
    }

    void Update(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        update(1, 1, n);
    }

    int Get(int l, int r)
    {
        u = l;
        v = r;
        if (l > r) return 0;
        return get(1, 1, n);
    }

    int Lower_bound(int l, int r, int val)
    {
        u = l;
        v = r;
        x = val;
        return lw(1, 1, n);
    }
} seg_mn;

int a[N];
vi pos[N];

int sequence(int n, vi arr) {
    for (int i = 1; i <= n; ++i) a[i] = arr[i - 1];
    for (int i = 1; i <= n; ++i) pos[i].clear();
    for (int i = 1; i <= n; ++i) pos[a[i]].eb(i);
    seg_mx.init(n);
    seg_mn.init(n);
    for (int i = 1; i <= n; ++i) {
        seg_mx.Update(i, n, -1);
        seg_mn.Update(i, n, -1);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int x : pos[i]) {
            seg_mx.Update(x, n, 2);
            seg_mn.Update(x, n, 2);
        }
        for (int j = 0; j < (int)pos[i].size(); ++j) {
            int x = pos[i][j];
            int vl = seg_mx.Get(x, x);
            int vr = seg_mx.Get(x, n);
            if (vr >= 0 && vl <= (j + 1) * 2) res = max(res, j + 1);
            else if (vr < 0) {
                int l = seg_mn.Lower_bound(1, x - 1, vr);
                if (l != -1) {
                    int t = upper_bound(all(pos[i]), l) - pos[i].begin();
                    res = max(res, j - t + 1);
                }
            }
        }
    }

    seg_mx.init(n);
    seg_mn.init(n);
    for (int i = 1; i <= n; ++i) {
        seg_mx.Update(i, n, 1);
        seg_mn.Update(i, n, 1);
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < (int)pos[i].size(); ++j) {
            int x = pos[i][j];
            int vl = seg_mx.Get(x, x);
            int vr = seg_mx.Get(x, n);
            if (vr >= 0 && vl <= (j + 1) * 2) res = max(res, j + 1);
            else if (vr < 0) {
                int l = seg_mn.Lower_bound(1, x - 1, vr);
                if (l != -1) {
                    int t = upper_bound(all(pos[i]), l) - pos[i].begin();
                    res = max(res, j - t + 1);
                }
            }
        }
        for (int x : pos[i]) {
            seg_mx.Update(x, n, -2);
            seg_mn.Update(x, n, -2);
        }
    }
    return res;
}

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