제출 #1326324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326324		trungcan	서열 (APIO23_sequence)	C++17	20 / 100	499 ms	44064 KiB

sequence

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

using namespace std;

const int M = 5e5 + 5;

int n, seg[M << 2][2];
int lazy[M << 2], ans = 0;
vector<int> P[M];

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 {M, -M};
    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)};
}

bool check(pii x, pii y, int val){
    if (x > y) swap(x, y);
    return y.fi - x.se <= val;
}

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

            int j = 0;
            for (int k = 0; k < (int)P[i].size(); ++k){
                pii cur = get(1, 0, n, 0, P[i][k] - 1);
                j = max(j, k);
                while (j < (int)P[i].size() && check(cur, get(1, 0, n, P[i][j], n), j - k + 1))
                    ++j;
                ans = max(ans, j - k);
            }

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

    return ans;
}

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