제출 #1183062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1183062		anmattroi	서열 (APIO23_sequence)	C++17	100 / 100	1159 ms	53848 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
#define maxn 500005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int a[maxn], n;
vector<int> nho[maxn];

int stMin[4*maxn], stMax[4*maxn], lz[4*maxn];

void apply(int r, int d) {
    stMin[r] += d;
    stMax[r] += d;
    lz[r] += d;
}

void down(int r) {
    if (lz[r]) {
        apply(r<<1, lz[r]);
        apply(r<<1|1, lz[r]);
        lz[r] = 0;
    }
}

void up(int r) {
    stMin[r] = min(stMin[r<<1], stMin[r<<1|1]);
    stMax[r] = max(stMax[r<<1], stMax[r<<1|1]);
}

void update(int u, int v, int d, int r = 1, int lo = 0, int hi = n) {
    if (u <= lo && hi <= v) {
        apply(r, d);
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, v, d, r<<1, lo, mid);
    if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
    up(r);
}

int getMin(int u, int v, int r = 1, int lo = 0, int hi = n) {
    if (u <= lo && hi <= v) return stMin[r];
    down(r);
    int mid = (lo + hi) >> 1;
    return min(u <= mid ? getMin(u, v, r<<1, lo, mid) : INT_MAX, v > mid ? getMin(u, v, r<<1|1, mid+1, hi) : INT_MAX);
}

int getMax(int u, int v, int r = 1, int lo = 0, int hi = n) {
    if (u <= lo && hi <= v) return stMax[r];
    down(r);
    int mid = (lo + hi) >> 1;
    return max(u <= mid ? getMax(u, v, r<<1, lo, mid) : INT_MIN, v > mid ? getMax(u, v, r<<1|1, mid+1, hi) : INT_MIN);
}

ii L[maxn], R[maxn];

int ok(int x) {
    for (int o = 1; o <= n; o++) {
        int sz = nho[o].size();
        for (int i = 0; i <= sz-x; i++) {
            int j = i+x-1;
            ii A = L[nho[o][i]], B = R[nho[o][j]],
               C = ii{max(B.fi-A.se, -x), min(B.se-A.fi, x)};
            if (C.fi <= C.se) return 1;
        }
    }
    return 0;
}

int mainProgram() {
    for (int i = 1; i <= n; i++) nho[a[i]].emplace_back(i);

    for (int i = 1; i <= n; i++) update(i, n, 1);

    for (int o = 1; o <= n; o++) {
        for (int i : nho[o]) update(i, n, -1);
        for (int i : nho[o]) L[i] = ii{getMin(0, i-1), getMax(0, i-1)};

        int sz = nho[o].size();


        for (int i = sz-1; i >= 0; i--) {
            int p = nho[o][i];
            R[p].fi = getMin(p, n);
            update(p, n, -1);
        }
        for (int i : nho[o]) update(i, n, 1);

        for (int i = sz-1; i >= 0; i--) {
            int p = nho[o][i];
            R[p].se = getMax(p, n);
            update(p, n, 1);
        }
        for (int i : nho[o]) update(i, n, -2);
    }
    int lo = 1, hi = n+1;
    while (hi-lo>1) {
        int mid = (lo+hi)>>1;
        if (ok(mid)) lo = mid;
        else hi = mid;
    }
    return lo;
}

int sequence(int N, vector<int> A) {
    n = N;
    for (int i = 0; i < N; i++) a[i+1] = A[i];
    return mainProgram();
}

• 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