제출 #1185313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1185313		duyngadocton	서열 (APIO23_sequence)	C++20	100 / 100	1478 ms	72828 KiB

sequence

#include<bits/stdc++.h>
#include "sequence.h"

using namespace std;

#define ii pair<int,int>
#define iii pair<ii,int>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ll long long

const int MAX = (int) 5e5;
const int inf = (int) 2e9;

int n, a[MAX + 5];
vector<int> pos[MAX + 5];
struct node {
    int u, v, l, r;
    node (int u = 0, int v = 0, int l = 0, int r = 0) : u(u), v(v), l(l), r(r) {}
} info[MAX + 5];

void maximize(int &x, int a) {
    if(a > x) x = a;
}

void minimize(int &x, int a) {
    if(a < x) x = a;
}

struct stmax {
    int st[MAX * 4 + 5];
    int lz[MAX * 4 + 5];

    void init() {
        for(int i = 1; i <= 4 * n + 4; ++i) st[i] = lz[i] = 0;
    }

    void fix(int id, int l, int r) {
        st[id] += lz[id];
        if(l != r) {
            lz[id * 2] += lz[id];
            lz[id * 2 + 1] += lz[id];
        }
        lz[id] = 0;
    }

    void upd(int id, int l, int r, int u, int v, int val) {
        fix(id, l, r);
        if(l > v || r < u) return;
        if(u <= l && r <= v) {
            lz[id] += val;
            fix(id, l, r);
            return ;
        }
        int mid = l + r >> 1;
        upd(id * 2, l, mid, u, v, val);
        upd(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = max(st[id * 2], st[id * 2 + 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(l > v || r < u) return -inf;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
} stmax;

struct stmin {
    int st[MAX * 4 + 5], lz[MAX * 4 + 5];

    void init() {
        for(int i = 1; i <= 4 * n + 4; ++i) st[i] = lz[i] = 0;
    }

    void fix(int id, int l, int r) {
        st[id] += lz[id];
        if(l != r) {
            lz[id * 2] += lz[id];
            lz[id * 2 + 1] += lz[id];
        }
        lz[id] = 0;
    }

    void upd(int id, int l, int r, int u, int v, int val) {
        fix(id, l, r);
        if(l > v || r < u) return;
        if(u <= l && r <= v) {
            lz[id] += val;
            fix(id, l, r);
            return ;
        }
        int mid = l + r >> 1;
        upd(id * 2, l, mid, u, v, val);
        upd(id * 2 + 1, mid + 1, r, u, v, val);
        st[id] = min(st[id * 2], st[id * 2 + 1]);
    }

    int get(int id, int l, int r, int u, int v) {
        fix(id, l, r);
        if(l > v || r < u) return inf;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return min(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }
} stmin;

bool f(int x) {
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < (int) pos[i].size(); ++j) {
            int k = j + x - 1;
            if(k < (int) pos[i].size()) {
                int L = info[pos[i][k]].l - info[pos[i][j]].v;
                int R = info[pos[i][k]].r - info[pos[i][j]].u;
                L = max(-x, L);
                R = min(R, x);
                if(L <= R) return true;
            }
        }
    }
    return false;
}

void build() {
    stmin.init();
    stmax.init();
    for(int i = 1; i <= n; ++i) pos[a[i]].pb(i);
    for(int i = 1; i <= n; ++i) stmax.upd(1, 0, n, i, n, 1), stmin.upd(1, 0, n, i, n, 1);
    for(int i = 1; i <= n; ++i) {
        for(int j : pos[i]) {
            stmax.upd(1, 0, n, j, n, -1);
            stmin.upd(1, 0, n, j, n, -1);
        }
        int cur = 0;
        for(int j = 0; j < (int) pos[i].size(); ++j) {
            info[pos[i][j]].u = stmin.get(1, 0, n, 0, pos[i][j] - 1);
//            if(cur == 0) minimize(info[pos[i][j]].u, 0);
            info[pos[i][j]].v = stmax.get(1, 0, n, 0, pos[i][j] - 1);
//            if(cur == 0) maximize(info[pos[i][j]].v, 0);
//            cur = pos[i][j];
        }
        for(int j = (int) pos[i].size() - 1; j >= 0; --j) {
            int x = pos[i][j];
            info[x].l = stmin.get(1, 0, n, x, n);
            stmin.upd(1, 0, n, x, n, -1);
        }
        for(int j = (int) pos[i].size() - 1; j >= 0; --j) {
            int x = pos[i][j];
            info[x].r = stmax.get(1, 0, n, x, n);
            stmax.upd(1, 0, n, x, n, 1);
        }
        for(int j : pos[i]) stmax.upd(1, 0, n, j, n, -2);
    }
}

int binary() {
    int lo = 0, hi = n + 1;
    while(hi - lo > 1) {
        int mid = lo + hi >> 1;
        if(f(mid)) lo = mid;
        else hi = mid;
    }
    return lo;
}

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

• 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