Submission #1131733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131733		antonn	서열 (APIO23_sequence)	C++17	100 / 100	1055 ms	72776 KiB

sequence

#include <bits/stdc++.h>

#define F first
#define S second

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 5e5+7;

int n, a[N];
vector<int> occ[N];

struct ST {
    int n;
    vector<pair<int, int>> t;
    vector<int> lazy;
    
    void init(int nn) {
        n = nn;
        t.assign(4 * n + 5, {0, 0});
        lazy.assign(4 * n + 5, 0);
    }
    
    pair<int, int> join(pair<int, int> a, pair<int, int> b) {
        pair<int, int> c;
        c.first = min(a.first, b.first);
        c.second = max(a.second, b.second);
        return c;
    }
    
    void push(int v, int tl, int tr) {
        if (tl < tr) {
            lazy[2 * v] += lazy[v];
            lazy[2 * v + 1] += lazy[v];
        }
        t[v].first += lazy[v];
        t[v].second += lazy[v];
        lazy[v] = 0;
    }
    
    void add(int v, int tl, int tr, int l, int r, int x) {
        push(v, tl, tr);
        if (l > tr || r < tl) return;
        if (l <= tl && tr <= r) {
            lazy[v] += x, push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) / 2;
        add(2 * v, tl, tm, l, r, x);
        add(2 * v + 1, tm + 1, tr, l, r, x);
        t[v] = join(t[2 * v], t[2 * v + 1]);
    }
    
    void add(int l, int r, int x) {
        add(1, 1, n + 1, l + 1, r + 1, x);
    }
    
    pair<int, int> get(int v, int tl, int tr, int l, int r) {
        push(v, tl, tr);
        if (l > tr || r < tl) return {1e9, -1e9};
        if (l <= tl && tr <= r) return t[v];
        int tm = (tl + tr) / 2;
        return join(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
    }
    
    int get_min(int l, int r) {
        return get(1, 1, n+1, l+1, r+1).first;
    }
    
    int get_max(int l, int r) {
        return get(1, 1, n+1, l+1, r+1).second;
    }
    
    pair<int, int> get(int l, int r) {
        return get(1, 1, n+1, l+1, r+1);
    }
    
    void clr() {
        for (int i = 1; i <= 4 * n + 4; ++i) t[i] = {0, 0}, lazy[i] = 0;
    }
};

ST t;

bool intersect(pair<int, int> a, pair<int, int> b) {
    if (a.second < b.first || a.first > b.second) return false;
    return true;
}

int sequence(int N, vector<int> A) {
    n = N;
    for (int i = 1; i <= n; ++i) a[i] = A[i - 1];
    for (int i = 1; i <= n; ++i) occ[a[i]].push_back(i);
    
    t.init(n);
    
    vector<pair<int, int>> pr(n + 1), sf(n + 1);
    vector<pair<int, int>> pr2(n + 1), sf2(n + 1);
    for (int i = 1; i <= n; ++i) t.add(i, n, 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (occ[i].empty()) continue;
        
        for (auto j : occ[i]) pr[j - 1] = t.get(0, j - 1);
        for (auto j : occ[i]) sf[j] = t.get(j, n);
        
        for (auto j : occ[i]) t.add(j, n, -2);
        
        for (auto j : occ[i]) pr2[j - 1] = t.get(0, j - 1);
        for (auto j : occ[i]) sf2[j] = t.get(j, n);
        
        
        int l = 1, r = occ[i].size(); 
        while (l <= r) {
            int m = (l + r) / 2;
            bool ok = 0;
            for (int j = 0; j + m - 1 < occ[i].size(); ++j) {
                int l = occ[i][j];
                int r = occ[i][j + m - 1];
                pair<int, int> a = pr[l - 1];
                pair<int, int> b = sf[r];
                pair<int, int> c = pr2[l - 1];
                pair<int, int> d = sf2[r];
                if (a.first <= b.second && b.first <= a.second) {
                    ok = 1;
                    break;
                }
                if (c.first <= d.second && d.first <= c.second) {
                    ok = 1;
                    break;
                }
                if (a.second <= b.first && d.second <= c.first) {
                    ok = 1;
                    break;
                }
                if (b.second <= a.first && c.second <= d.first) {
                    ok = 1;
                    break;
                }
            }
            if (ok == 1) l = m + 1;
            if (ok == 0) r = m - 1;
        }
        ckmax(ans, l - 1);
    }
    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