제출 #1095110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1095110		RiverFlow	서열 (APIO23_sequence)	C++17	31 / 100	611 ms	102348 KiB

sequence

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b or a == -1) { a = b; return 1; } return 0;
}

const int N = (int)5e5 + 7;

int n, a[N];

struct IT {
    int n;
    vec<ii> t;
    vec<int> lz;
    IT (){};
    IT (int _n) {
        n = _n;
        lz.resize(4 * n + 7);
        t.resize(4 * n + 7);
    }
    vec<int> a;
    void refine(int id) {
        t[id].fi = min(t[id << 1].fi, t[id << 1 | 1].fi);
        t[id].se = max(t[id << 1].se, t[id << 1 | 1].se);
    }
    void build(int id, int l, int r) {
        if (l == r) {
            return void(t[id]=_mp(a[l], a[l]));
        }
        int m = (l + r) >> 1;
        build(id << 1, l, m);
        build(id << 1 | 1, m + 1, r);
        refine(id);
    }
    void init(vec<int> p){
        a.resize(n + 1);
        FOR(i, 1, n) a[i] = p[i];
        build(1, 1, n);
    }
    void push(int id) {
        int &x = lz[id];
        t[id<<1].fi+=x;
        t[id<<1|1].fi+=x;
        t[id<<1].se+=x;
        t[id<<1|1].se+=x;
        lz[id<<1]+=x;
        lz[id<<1|1]+=x;
        x=0;
    }
    void update(int id, int l, int r, int u, int v, int val) {
        if (l > v or r < u) return ;
        if (l >= u and r <= v) {
            t[id].fi += val;
            t[id].se += val;
            lz[id] += val;
            return ;
        }
        if (lz[id]) {
            push(id);
        }
        int m = (l + r) >> 1;
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);
        refine(id);
    }
    void update(int l, int r, int v) {
        if (l > r) return ;
        update(1, 1, n, l, r, v);
    }
    ii get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) {
            return _mp(n, -n);
        }
        if (l >= u and r <= v)
            return t[id];
        if (lz[id]) {
            push(id);
        }
        int m = (l + r) >> 1;
        ii A = get(id << 1, l, m, u, v);
        ii B = get(id << 1 | 1, m + 1, r, u, v);
        return _mp(min(A.fi, B.fi), max(A.se, B.se));
    }
    ii get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};
vec<int> pos[N];

struct segment_tree {
    int n;
    vector<int> t, lz;
    segment_tree () {};
    segment_tree (int _n) {
        n = _n;
        t.assign(4 * n + 7, n + 1);
        lz.assign(4 * n + 7, -1);
    }
    void push(int id) {
        int &x = lz[id];
        mini(t[id << 1], x);
        mini(t[id << 1 | 1], x);
        mini(lz[id << 1], x);
        mini(lz[id << 1 | 1], x);
        x = -1;
    }
    void upd(int id, int l, int r, int u, int v, int val) {
        if (l > v or r < u) return ;
        t[id] = min(t[id], val);
        if (l >= u and r <= v) {
            mini(lz[id], val);
            return ;
        }
        if (lz[id] != -1) {
            push(id);
        }
        int m = (l + r) >> 1;
        upd(id << 1, l, m, u, v, val);
        upd(id << 1 | 1, m + 1, r, u, v, val);
    }
    void upd(int l, int r, int val) {
        upd(1, 1, n, l, r, val);
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return n;
        if (l >= u and r <= v) return t[id];
        int m = (l + r) >> 1;
        if (lz[id] != -1) {
            push(id);
        }
        return min(get(id << 1, l, m, u, v), get(id << 1 | 1, m + 1, r, u, v));
    }
    int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

ii A[N], B[N];

namespace SUB_FULL {
int sol() {
    int ans = 1;
    FOR(i, 1, n) {
        pos[a[i]].push_back(i);
    }
    IT st1(n), st2(n);
    vec<int> p(n+1,0);
    FOR(i,1,n)p[i]=-(i-1);
    st1.init(p); // pref(l-1)
    FOR(i,1,n)p[i]=-i;
    st2.init(p); // pref(r)

    FOR(i, 1, n) if (sz(pos[i])) {
        if (sz(pos[i]) > 1) {
            vec<int> &c = pos[i];
            for(int j = 0; j < sz(c); ++j) {
                A[j] = st1.get(1, c[j]);
                B[j] = st2.get(c[j], n);
            }
            vec<int> cord;
            auto key = [&](int val) -> int {
                return lower_bound(all(cord), val) - cord.begin() + 1;
            };
            for(int j = 0; j < sz(c); ++j) {
                cord.push_back(A[j].fi + 2 * j - 2);
                cord.push_back(A[j].second);
                cord.push_back(B[j].se + 2 * j);
                cord.push_back(B[j].fi);
            }
            unq(cord);
            segment_tree st(sz(cord));
            for(int j = 0; j < sz(c); ++j) {
                if (j > 0) {
                    int L = key(B[j].fi);
                    int R = key(B[j].se + 2 * j);
//                    cerr << j << ' ' << st.get(L, R) << nl;
                    ans = max(ans, j - st.get(L, R) + 1);
                }
                int L = key(A[j].fi + 2 * j - 2);
                int R = max(L, key(A[j].se));
                st.upd(L, R, j);
            }
        }
        for(int j : pos[i]) {
            //pref(j+1) duoc cong them 2
            st1.update(j + 1, n, 2);
            st2.update(j, n, 2);
        }
    }
    return ans;
}
};
int sequence(int N, vector<int> A) {
    n = N;
    FOR(i, 1, n) a[i] = A[i - 1];
    return SUB_FULL::sol();
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    int n; cin >> n;
    vector<int> a(n);
    for(int & x : a) cin >> x;
    cout << sequence(n, a);
}
#endif LOCAL

컴파일 시 표준 에러 (stderr) 메시지

sequence.cpp:231:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
  231 | #endif LOCAL
      |        ^~~~~

• Subtask 1: 11 / 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