#735262 (C++17) No.1827 最長部分スーパーリッチ門松列列

提出ソース

結果

問題	No.1827 最長部分スーパーリッチ門松列列
ユーザー	fuppy_kyopro
提出日時	2022-01-28 22:37:31
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	11,179 bytes
コンパイル時間	3,562 ms
コンパイル使用メモリ	234,980 KB
実行使用メモリ	39,788 KB
最終ジャッジ日時	2024-06-09 15:58:00
合計ジャッジ時間	11,798 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,756 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	49 ms 6,940 KB
testcase_04	AC	1,540 ms 6,940 KB
testcase_05	AC	1,487 ms 6,940 KB
testcase_06	AC	1,504 ms 6,940 KB
testcase_07	TLE	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//*/

#include <bits/stdc++.h>

// #include <atcoder/all>

using namespace std;
// using namespace atcoder;

#define DEBUG(x) cerr << #x << ": " << x << endl;
#define DEBUG_VEC(v)                                        \
    cerr << #v << ":";                                      \
    for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \
        cerr << " " << v[iiiiiiii];                         \
    cerr << endl;
#define DEBUG_MAT(v)                                \
    cerr << #v << endl;                             \
    for (int iv = 0; iv < v.size(); iv++) {         \
        for (int jv = 0; jv < v[iv].size(); jv++) { \
            cerr << v[iv][jv] << " ";               \
        }                                           \
        cerr << endl;                               \
    }
typedef long long ll;
// #define int ll

#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define vs vector<string>
#define pii pair<int, int>
#define pis pair<int, string>
#define psi pair<string, int>
#define pll pair<ll, ll>
template <class S, class T>
pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) {
    return pair<S, T>(s.first + t.first, s.second + t.second);
}
template <class S, class T>
pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template <class S, class T>
ostream &operator<<(ostream &os, pair<S, T> p) {
    os << "(" << p.first << ", " << p.second << ")";
    return os;
}
#define X first
#define Y second
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--)
#define rrep1(i, n) for (int i = (int)(n); i > 0; i--)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(), c.end()
void YES(bool t = true) {
    cout << (t ? "YES" : "NO") << endl;
}
void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; }
void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; }
void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; }
void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; }
void no(bool t = true) { cout << (t ? "no" : "yes") << endl; }
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
#define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const long double pi = 3.1415926535897932384626433832795028841971L;
int popcount(ll t) { return __builtin_popcountll(t); }
// int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
// int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
vi dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1};
struct Setup_io {
    Setup_io() {
        ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        cout << fixed << setprecision(25);
    }
} setup_io;
// const ll MOD = 1000000007;
const ll MOD = 998244353;
// #define mp make_pair
//#define endl '\n'
template <typename T>
class SegmentTree {
  public:
    using F = function<T(T &, T &)>;
    int n;
    vector<T> dat;
    T e;
    F query_func;
    F update_func;

    SegmentTree(vector<T> a, F query_func, F update_func, T e) : n(a.size()), query_func(query_func), update_func(update_func), e(e) {
        if (n == 0) {
            a.push_back(e);
            n++;
        }
        dat.resize(4 * n);
        init(0, 0, n, a);
    }

    void init(int k, int l, int r, vector<T> &a) {
        if (r - l == 1) {
            dat[k] = a[l];
        } else {
            int lch = 2 * k + 1, rch = 2 * k + 2;
            init(lch, l, (l + r) / 2, a);
            init(rch, (l + r) / 2, r, a);
            dat[k] = query_func(dat[lch], dat[rch]);
        }
    }

    void update(int k, T a, int v, int l, int r) {
        if (r - l == 1) {
            dat[v] = update_func(dat[v], a);
        } else {
            if (k < (l + r) / 2)
                update(k, a, 2 * v + 1, l, (l + r) / 2);
            else {
                update(k, a, 2 * v + 2, (l + r) / 2, r);
            }
            dat[v] = query_func(dat[v * 2 + 1], dat[v * 2 + 2]);
        }
    }

    void update(int k, T a) {
        update(k, a, 0, 0, n);
    }

    T query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return e;
        }
        if (a <= l && r <= b) {
            return dat[k];
        } else {
            T ul = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T ur = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return query_func(ul, ur);
        }
    }

    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }

    int find(int a, int b, int k, int l, int r, int x) {
        if (dat[k] < x || r <= a || b <= l) return -1;
        if (l + 1 == r) {
            if (dat[k] >= x)
                return l;
            else
                return -1;
        }
        int rv = find(a, b, 2 * k + 1, l, (l + r) / 2, x);
        if (rv != -1) return rv;
        return find(a, b, 2 * k + 2, (l + r) / 2, r, x);
    }

    int find2(int a, int b, int k, int l, int r, int x) {
        if (dat[k] == r - l || r <= a || b <= l) return -1;
        if (l + 1 == r) {
            if (dat[k] == 0)
                return l;
            else
                return -1;
        }
        int rv = find2(a, b, 2 * k + 1, l, (l + r) / 2, x);
        if (rv != -1) return rv;
        return find2(a, b, 2 * k + 2, (l + r) / 2, r, x);
    }
};

template <typename T1, typename T2>
class LazySegmentTree {
  public:
    using F = function<T1(T1 &, T1 &)>;           // query_func
    using G = function<T2(T2 &, T2 &)>;           // update_func
    using H = function<T1(T1 &, T2 &, int, int)>; // lazy to node (node, lazy, left, right)
    int n;
    vector<T1> node;
    vector<T2> lazy;
    T1 e1;
    T2 e2;
    F query_func;
    G update_func;
    H eval_func;

    LazySegmentTree(vector<T1> a, F query_func, G update_func, H eval_func, T1 e1, T2 e2)
        : query_func(query_func), update_func(update_func), eval_func(eval_func), e1(e1), e2(e2) {
        int _n = a.size();
        n = 1;
        while (n < _n)
            n *= 2;
        node.resize(2 * n - 1, e1);
        lazy.resize(2 * n - 1, e2);
        for (int i = 0; i < _n; i++)
            node[i + n - 1] = a[i];
        for (int i = n - 2; i >= 0; i--) {
            node[i] = query_func(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    // k�Ԗڂ̃m�[�h�ɂ��Ēx���]�����s��
    inline void eval(int k, int l, int r) {
        if (lazy[k] != e2) { // Change
            node[k] = eval_func(node[k], lazy[k], l, r);
            if (r - l > 1) {
                lazy[2 * k + 1] = update_func(lazy[2 * k + 1], lazy[k]);
                lazy[2 * k + 2] = update_func(lazy[2 * k + 2], lazy[k]);
            }
            lazy[k] = e2; // Change
        }
    }

    // [a, b)��x�ɂ���
    void update(int a, int b, T2 x, int k, int l, int r) {
        // k �Ԗڂ̃m�[�h�ɑ΂��Ēx���]�����s��
        eval(k, l, r);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] = update_func(lazy[k], x);
            eval(k, l, r);
        } else {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = query_func(node[2 * k + 1], node[2 * k + 2]);
        }
    }

    T1 query(int a, int b, int k, int l, int r) {
        eval(k, l, r);
        if (b <= l || r <= a) return e1;
        if (a <= l && r <= b) return node[k];
        T1 resl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T1 resr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return query_func(resl, resr);
    }

    T1 query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

int f(int a, int b) { return a + b; }
int g(int a, int b) { return b; }
int h(int a, int b, int l, int r) { return b * (r - l); }

int pre_use(LazySegmentTree<int, int> &use, int i) {
    // i 以前初めての use (i 含まず)
    if (use.query(0, i) == 0) return -1;

    int ok = 0, ng = i;
    while (ok + 1 < ng) {
        int mid = (ok + ng) / 2;
        if (use.query(mid, i) == 0)
            ng = mid;
        else
            ok = mid;
    }
    return ok;
}

int nex0(SegmentTree<int> &val, int i, int n) {
    // i 以降初めての 0 (i 含む)
    if (val.query(i, n) == n - i) return n;
    return val.find2(i, n, 0, 0, n, 0);

    int ng = i, ok = n;
    while (ng + 1 < ok) {
        int mid = (ng + ok) / 2;
        if (val.query(i, mid) == mid - i)
            ng = mid;
        else
            ok = mid;
    }
    return ok - 1;
}

int nex1(SegmentTree<int> &val, int i, int n) {
    // i 以降初めての 1 (i 含む)
    if (val.query(i, n) == 0) return n;
    return val.find(i, n, 0, 0, val.n, 1);

    int ng = i, ok = n;
    while (ng + 1 < ok) {
        int mid = (ng + ok) / 2;
        if (val.query(i, mid) == 0)
            ng = mid;
        else
            ok = mid;
    }
    return ok - 1;
}

int calc(int n, vi p) {
    vi ini1(n);
    SegmentTree<int> val(ini1, f, g, 0);

    vi ini2(n);
    ini2[0] = 1;
    LazySegmentTree<int, int> use(ini2, f, g, h, 0, -1);

    vector<pii> pi(n);
    rep(i, n) pi[i] = pii(p[i], i);
    sort(all(pi));
    int ans = 1;

    for (auto [_, i] : pi) {
        val.update(i, 1);
        use.update(i, i + 1, 0, 0, 0, use.n);

        int idx = pre_use(use, i);
        int x = val.query(idx, idx + 1);
        idx++;

        while (idx < n) {
            // rep(i, n) cout << val.query(i, i + 1) << " ";
            // cout << endl;

            // DEBUG(pii(idx, x));
            int y = 1 - x;
            int nidx;
            if (y == 0) {
                nidx = nex0(val, idx, n);
            } else {
                nidx = nex1(val, idx, n);
            }
            // DEBUG(nidx);

            if (idx != nidx) {
                use.update(idx, nidx, 0, 0, 0, use.n);
            }
            if (nidx == n) break;
            if (use.query(nidx, nidx + 1) == 1) break;

            use.update(nidx, nidx + 1, 1, 0, 0, use.n);
            idx = nidx + 1;
            x = y;
        }

        chmax(ans, use.query(0, n));
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    vi p(n);
    rep(i, n) {
        cin >> p[i];
        // p[i] = i + 1;
        p[i]--;
    }
    // std::random_device seed_gen;
    // std::mt19937 engine(seed_gen());
    // std::shuffle(p.begin(), p.end(), engine);

    int ans = calc(n, p);
    rep(i, n) {
        p[i] = n - 1 - p[i];
    }
    chmax(ans, calc(n, p));
    cout << ans << endl;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

yukicoder

結果

テストケース

ソースコード