Submission #1326546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326546		trungcan	Sequence (APIO23_sequence)	C++17	100 / 100	741 ms	52528 KiB

sequence

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second

using namespace std;

const int M = 16e5 + 5, LIMN = 5e5 + 5;
const int INF = 1e9 + 7;

int n, seg[LIMN << 2][2];
int fen[M][2];
int lazy[LIMN << 2], ans = 1;
vector<int> P[LIMN];
vector<piii> L, R;

void build(int id, int l, int r){
    if (l == r){
        seg[id][0] = seg[id][1] = l;
        return;
    }

    int mid = l + ((r - l) >> 1);

    build(id << 1, l, mid); build((id << 1) | 1, mid + 1, r);

    seg[id][0] = min(seg[id << 1][0], seg[(id << 1) | 1][0]);
    seg[id][1] = max(seg[id << 1][1], seg[(id << 1) | 1][1]);
}

void down(int id){
    int &v = lazy[id];
    seg[id << 1][0] += v; seg[id << 1][1] += v;
    seg[(id << 1) | 1][0] += v; seg[(id << 1) | 1][1] += v;
    lazy[id << 1] += v; lazy[(id << 1) | 1] += v;

    v = 0;
}

void update(int id, int l, int r, int u, int v, int val){
    if (r < u || v < l) return;
    if (u <= l && r <= v){
        seg[id][0] += val;
        seg[id][1] += val;
        lazy[id] += val;
        return;
    }

    if (lazy[id]) down(id);
    int mid = l + ((r - l) >> 1);

    update(id << 1, l, mid, u, v, val);
    update((id << 1) | 1, mid + 1, r, u, v, val);

    seg[id][0] = min(seg[id << 1][0], seg[(id << 1) | 1][0]);
    seg[id][1] = max(seg[id << 1][1], seg[(id << 1) | 1][1]);
}

pii get(int id, int l, int r, int u, int v){
    if (r < u || v < l) return {LIMN, -LIMN};
    if (u <= l && r <= v) return {seg[id][0], seg[id][1]};

    if (lazy[id]) down(id);
    int mid = l + ((r - l) >> 1);

    pii t1 = get(id << 1, l, mid, u, v),
        t2 = get((id << 1) | 1, mid + 1, r, u, v);

    return {min(t1.fi, t2.fi), max(t1.se, t2.se)};
}

void upfen(int x, int val, int k, bool t){
    x += LIMN;
    if (!k){
        if (!t)
            for (; x > 0; x -= x & -x)
                fen[x][k] = min(fen[x][k], val);
        else
            for (; x > 0; x -= x & -x)
                fen[x][k] = val;
    } else {
        if (!t)
            for (; x <= n + LIMN; x += x & -x)
                fen[x][k] = min(fen[x][k], val);
        else
            for (; x <= n + LIMN; x += x & -x)
                fen[x][k] = val;
    }
}

int gf(int x, int k){
    int res = INF;
    x += LIMN;
    if (!k)
        for (; x <= n + LIMN; x += x & -x)
            res = min(res, fen[x][k]);
    else
        for (; x > 0; x -= x & -x)
            res = min(res, fen[x][k]);
    return res;
}

int sequence(int N, vector<int> A){
    ios_base::sync_with_stdio(0); cin.tie(0);
    n = N;
    for (int i = 0; i < n; ++i) P[A[i]].push_back(i + 1);

    build(1, 0, n);

    for (int i = 1; i <= LIMN + n; ++i)
        fen[i][0] = fen[i][1] = INF;

    for (int i = 1; i <= n; ++i)
        if ((int)P[i].size()){
            for (int x: P[i])
                update(1, 0, n, x, n, -1);

            for (int k = 0; k < (int)P[i].size(); ++k){
                pii x = get(1, 0, n, 0, P[i][k] - 1),
                    y = get(1, 0, n, P[i][k], n);
                L.push_back({x, k}); R.push_back({y, k});
            }

            sort(L.begin(), L.end()); sort(R.begin(), R.end());

            int j = 0;
            for (piii x: R){
                while (j < (int)L.size() && L[j].fi.fi <= x.fi.fi){
                    upfen(L[j].fi.se - (L[j].se - 1), L[j].se, 0, 0);
                    ++j;
                }

                ans = max(ans, x.se - gf(x.fi.fi - x.se, 0) + 1);
            }

            for (int k = 0; k < j; ++k)
                upfen(L[k].fi.se - (L[k].se - 1), INF, 0, 1);

            j = (int)L.size() - 1;
            for (int k = (int)R.size() - 1; k >= 0; --k){
                piii x = R[k];
                while (j >= 0 && L[j].fi.fi > x.fi.fi){
                    upfen(L[j].fi.fi + (L[j].se - 1), L[j].se, 1, 0);
                    --j;
                }
                ans = max(ans, x.se - gf(x.fi.se + x.se, 1) + 1);
            }

            for (int k = j + 1; k < (int)L.size(); ++k)
                upfen(L[k].fi.fi + (L[k].se - 1), INF, 1, 1);

            for (int x: P[i])
                update(1, 0, n, x, n, -1);

            L.clear(); R.clear();
        }

    return ans;
}

• 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: 18 / 18