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

提出ソース
結果

問題	No.1827 最長部分スーパーリッチ門松列列
ユーザー	mai
提出日時	2021-09-18 01:01:46
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	TLE (最新) AC (最初)
実行時間	-
コード長	16,192 bytes
コンパイル時間	4,842 ms
コンパイル使用メモリ	249,368 KB
実行使用メモリ	68,936 KB
最終ジャッジ日時	2023-09-29 03:32:17
合計ジャッジ時間	24,147 ms
ジャッジサーバーID （参考情報）	judge11 / judge13
このコードへのチャレンジ（β）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 8,760 KB
testcase_01	AC	2 ms 4,376 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	18 ms 4,376 KB
testcase_04	AC	425 ms 4,376 KB
testcase_05	AC	424 ms 4,376 KB
testcase_06	AC	425 ms 4,376 KB
testcase_07	AC	1,344 ms 67,492 KB
testcase_08	AC	1,346 ms 67,292 KB
testcase_09	AC	1,340 ms 67,572 KB
testcase_10	AC	1,342 ms 67,388 KB
testcase_11	AC	1,344 ms 67,580 KB
testcase_12	AC	1,328 ms 67,492 KB
testcase_13	AC	1,330 ms 67,580 KB
testcase_14	AC	1,403 ms 67,356 KB
testcase_15	AC	1,396 ms 67,452 KB
testcase_16	AC	1,399 ms 67,360 KB
testcase_17	TLE	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

#define all(v) (v).begin(), (v).end()
#define repeat(cnt, l)                                                         \
  for (typename remove_const<                                                  \
           typename remove_reference<decltype(l)>::type>::type cnt = {};       \
       (cnt) < (l); ++(cnt))
#define rrepeat(cnt, l) for (auto cnt = (l)-1; 0 <= (cnt); --(cnt))
#define iterate(cnt, b, e) for (auto cnt = (b); (cnt) != (e); ++(cnt))
#define increase(cnt, b, e) for (auto cnt = (b); (cnt) < (e); ++(cnt))
#define decrease(cnt, b, e) for (auto cnt = (b); (e) <= (cnt); --(cnt))
const long long MD = 1000000007ll;
const long double PI = 3.1415926535897932384626433832795L;
template <typename T1, typename T2>
inline ostream &operator<<(ostream &o, const pair<T1, T2> p) {
  o << '(' << p.first << ':' << p.second << ')';
  return o;
}
template <typename T> inline T &chmax(T &to, const T &val) {
  return to = max(to, val);
}
template <typename T> inline T &chmin(T &to, const T &val) {
  return to = min(to, val);
}
void bye(string s, int code = 0) {
  cout << s << endl;
  exit(code);
}
mt19937_64 randdev(8901016);
template <typename T, typename Random = decltype(randdev),
          typename enable_if<is_integral<T>::value>::type * = nullptr>
inline T rand(T l, T h, Random &rand = randdev) {
  return uniform_int_distribution<T>(l, h)(rand);
}
template <typename T, typename Random = decltype(randdev),
          typename enable_if<is_floating_point<T>::value>::type * = nullptr>
inline T rand(T l, T h, Random &rand = randdev) {
  return uniform_real_distribution<T>(l, h)(rand);
}
template <typename T>
static ostream &operator<<(ostream &o, const std::vector<T> &v) {
  o << "[ ";
  for (const auto &e : v)
    o << e << ' ';
  return o << ']';
}

template <typename I> struct MyRangeFormat {
  I b, e;
  MyRangeFormat(I _b, I _e) : b(_b), e(_e) {}
};
template <typename I>
static ostream &operator<<(ostream &o, const MyRangeFormat<I> &f) {
  o << "[ ";
  iterate(i, f.b, f.e) o << *i << ' ';
  return o << ']';
}
template <typename I> struct MyMatrixFormat {
  const I &p;
  long long n, m;
  MyMatrixFormat(const I &_p, long long _n, long long _m)
      : p(_p), n(_n), m(_m) {}
};
template <typename I>
static ostream &operator<<(ostream &o, const MyMatrixFormat<I> &f) {
  o << '\n';
  repeat(i, (f.n)) {
    repeat(j, f.m) o << f.p[i][j] << ' ';
    o << '\n';
  }
  return o;
}
struct LOG_t {
  ~LOG_t() { cout << endl; }
};
#define LOG (LOG_t(), cout << 'L' << __LINE__ << ": ")
#define FMTA(m, w) (MyRangeFormat<decltype(m + 0)>(m, m + w))
#define FMTR(b, e) (MyRangeFormat<decltype(e)>(b, e))
#define FMTV(v) FMTR(v.begin(), v.end())
#define FMTM(m, h, w) (MyMatrixFormat<decltype(m + 0)>(m, h, w))

#if defined(_WIN32) || defined(_WIN64)
#define getc_x _getc_nolock
#define putc_x _putc_nolock
#elif defined(__GNUC__)
#define getc_x getc_unlocked
#define putc_x putc_unlocked
#else
#define getc_x getc
#define putc_x putc
#endif
class MaiScanner {
  FILE *fp_;
  constexpr bool isvisiblechar(char c) noexcept {
    return (0x21 <= (c) && (c) <= 0x7E);
  }

public:
  inline MaiScanner(FILE *fp) : fp_(fp) {}
  template <typename T> void input_integer(T &var) noexcept {
    var = 0;
    T sign = 1;
    int cc = getc_x(fp_);
    for (; cc < '0' || '9' < cc; cc = getc_x(fp_))
      if (cc == '-')
        sign = -1;
    for (; '0' <= cc && cc <= '9'; cc = getc_x(fp_))
      var = (var << 3) + (var << 1) + cc - '0';
    var = var * sign;
  }
  inline int c() noexcept { return getc_x(fp_); }
  template <typename T, typename enable_if<is_integral<T>::value,
                                           nullptr_t>::type = nullptr>
  inline MaiScanner &operator>>(T &var) noexcept {
    input_integer<T>(var);
    return *this;
  }
  inline MaiScanner &operator>>(string &var) {
    int cc = getc_x(fp_);
    for (; !isvisiblechar(cc); cc = getc_x(fp_))
      ;
    for (; isvisiblechar(cc); cc = getc_x(fp_))
      var.push_back(cc);
    return *this;
  }
  template <typename IT> inline void in(IT begin, IT end) {
    for (auto it = begin; it != end; ++it)
      *this >> *it;
  }
};
class MaiPrinter {
  FILE *fp_;

public:
  inline MaiPrinter(FILE *fp) : fp_(fp) {}
  template <typename T> void output_integer(T var) noexcept {
    if (var == 0) {
      putc_x('0', fp_);
      return;
    }
    if (var < 0)
      putc_x('-', fp_), var = -var;
    char stack[32];
    int stack_p = 0;
    while (var)
      stack[stack_p++] = '0' + (var % 10), var /= 10;
    while (stack_p)
      putc_x(stack[--stack_p], fp_);
  }
  inline MaiPrinter &operator<<(char c) noexcept {
    putc_x(c, fp_);
    return *this;
  }
  template <typename T, typename enable_if<is_integral<T>::value,
                                           nullptr_t>::type = nullptr>
  inline MaiPrinter &operator<<(T var) noexcept {
    output_integer<T>(var);
    return *this;
  }
  inline MaiPrinter &operator<<(char *str_p) noexcept {
    while (*str_p)
      putc_x(*(str_p++), fp_);
    return *this;
  }
  inline MaiPrinter &operator<<(const string &str) {
    const char *p = str.c_str();
    const char *l = p + str.size();
    while (p < l)
      putc_x(*p++, fp_);
    return *this;
  }
  template <typename IT> void join(IT begin, IT end, char sep = ' ') {
    for (bool b = 0; begin != end; ++begin, b = 1)
      b ? *this << sep << *begin : *this << *begin;
  }
};
MaiScanner scanner(stdin);
MaiPrinter printer(stdout);

//

class SquareRootDecomposition {
  struct Node {
    int add_;
    shared_ptr<vector<int>> data_;

    int get(int i) const { return data_->operator[](i) + add_; }
    int set(int i, int x) {
      apply();
      return data_->operator[](i) = x;
    }

    void apply() {
      // データが複数のNodeから参照されているならば
      if (data_.use_count() > 1) {
        // O(M)時間で複製する
        data_ = make_shared<vector<int>>(*data_);
      }
      // add_を適用する。
      if (add_ == 0)
        return;
      for (auto &e : *data_)
        e += add_;
      add_ = 0;
    }
    void copyNode(Node &src) {
      add_ = src.add_;
      // note: 参照をコピーするのでO(1)時間で完了する
      data_ = src.data_;
    }
  };

  int M_;
  vector<Node> nodes_;

public:
  SquareRootDecomposition(int sqrtN) : M_(sqrtN), nodes_(sqrtN) {}
  void fill(int x) {
    for (Node &node : nodes_) {
      node.add_ = 0;
      node.data_ = make_shared<vector<int>>(M_, x);
    }
  }
  int getValue(int i) const {
    const auto &node = nodes_[i / M_];
    int x = node.get(i % M_);
    return x;
  }
  void addValueRange(int be, int en, int x) {
    if (be >= en)
      return;
    while (be / M_ * M_ != be) {
      auto &node = nodes_[be / M_];
      node.set(be % M_, node.get(be % M_) + x);
      if (++be >= en)
        return;
    }
    while (be / M_ != en / M_) {
      auto &node = nodes_[be / M_];
      node.add_ += x;
      if ((be += M_) >= en)
        return;
    }
    while (be < en) {
      auto &node = nodes_[be / M_];
      node.set(be % M_, node.get(be % M_) + x);
      ++be;
    }
  }
  void copyValueRange(int be, int en, SquareRootDecomposition &src) {
    if (be >= en)
      return;
    while (be / M_ * M_ != be) {
      auto &node = nodes_[be / M_];
      auto &src_node = src.nodes_[be / M_];
      node.set(be % M_, src_node.get(be % M_));
      if (++be >= en)
        return;
    }
    while (be / M_ != en / M_) {
      auto &node = nodes_[be / M_];
      auto &src_node = src.nodes_[be / M_];
      node.copyNode(src_node);
      if ((be += M_) >= en)
        return;
    }
    while (be < en) {
      auto &node = nodes_[be / M_];
      auto &src_node = src.nodes_[be / M_];
      node.set(be % M_, src_node.get(be % M_));
      ++be;
    }
  }
};

class SegmentTree {

  class Node {

    shared_ptr<Node> copyNode() {
      shared_ptr<Node> new_node = make_shared<Node>(add_);
      new_node->left_ = left_; // share childlen
      new_node->right_ = right_;
      return new_node;
    }

    void toOwnedChild() {
      toOwnedChild(left_);
      toOwnedChild(right_);
    }
    void toOwnedChild(shared_ptr<Node> &child) {
      if (!child) {
        child = make_shared<Node>(0);
      } else if (child.use_count() >= 2) {
        auto new_child = child->copyNode();
        child = move(new_child);
      }
    }

  public:
    int add_;
    shared_ptr<Node> left_, right_;

    Node(int val) : add_(val), left_(), right_() {}

    bool hasChild() const { return left_ || right_; }
    void applyDownLazy() {
      toOwnedChild();
      left_->add_ += add_;
      right_->add_ += add_;
      add_ = 0;
    }
  };

  int N_;
  shared_ptr<Node> root;

public:
  SegmentTree(int least_n) : N_(), root(new Node(0)) {
    N_ = 8;
    while (N_ < least_n)
      N_ <<= 1;
  }

  void addValueRange(int be, int en, int x) {
    addValueRangeInternal(be, en, x, root, 0, N_);
  }

  void addValueRangeInternal(int dst_be, int dst_en, int x,
                             shared_ptr<Node> &node, int be, int en) {
    // static int call = 0;
    // if (++call > 99)
    //   abort();
    // LOG << be << " " << en << "/" << dst_be << " " << dst_en;
    if (dst_be <= be && en <= dst_en) {
      node->add_ += x;
    } else if (dst_be < en && be < dst_en) {
      node->applyDownLazy();
      int m = (be + en) / 2;
      addValueRangeInternal(dst_be, dst_en, x, node->left_, be, m);
      addValueRangeInternal(dst_be, dst_en, x, node->right_, m, en);
    }
  }

  void copyValueRange(int be, int en, SegmentTree &src) {
    copyValueRangeInternal(be, en, src.root, root, 0, N_);
  }

  void copyValueRangeInternal(int dst_be, int dst_en, shared_ptr<Node> &src,
                              shared_ptr<Node> &node, int be, int en) {
    // static int call = 0;
    // if (++call > 99)
    //   abort();
    // LOG << be << " " << en << "/" << dst_be << " " << dst_en;
    if (dst_be <= be && en <= dst_en) {
      node = src;
    } else if (dst_be < en && be < dst_en) {
      node->applyDownLazy();
      src->applyDownLazy();
      int m = (be + en) / 2;
      copyValueRangeInternal(dst_be, dst_en, src->left_, node->left_, be, m);
      copyValueRangeInternal(dst_be, dst_en, src->right_, node->right_, m, en);
    }
  }

  int getValue(int i) {
    int be = 0, en = N_;
    Node *node = root.get();
    int val = node->add_;
    while (node->hasChild()) {
      int m = (be + en) / 2;
      if (i < m) {
        node = node->left_.get();
        en = m;
      } else {
        node = node->right_.get();
        be = m;
      }
      val += node->add_;
    }
    return val;
  }
};

//

struct Problem {
  int N;
  vector<int> A;

  void set(const Problem &p) {
    N = p.N;
    A = p.A;
  }

  void scan() {
    scanner >> N;
    A.resize(N);
    A.shrink_to_fit();
    scanner.in(all(A));
  }

  void generate(int n) {
    N = n;
    A.resize(N);
    A.shrink_to_fit();
    iota(all(A), 1);
    shuffle(all(A), randdev);
  }

  virtual int solve() { return -1; };
};

//

struct ProblemSolverExp : public Problem {
  int solve() override {
    if (N > 24)
      return -1;

    int best_len = 1;
    // 全列挙
    for (int b = 1; b < (1 << N); ++b) {
      // ビット列から部分列を生成
      vector<int> aa;
      repeat(i, N) if (b & (1 << i)) aa.push_back(A[i]);
      if (aa.size() <= 1)
        continue;

      // 評価
      int even_min = numeric_limits<int>::max();
      int odd_max = 0;
      int even_max = 0;
      int odd_min = numeric_limits<int>::max();
      repeat(j, int(aa.size())) {
        if (j & 1) {
          chmin(odd_min, aa[j]);
          chmax(odd_max, aa[j]);
        } else {
          chmin(even_min, aa[j]);
          chmax(even_max, aa[j]);
        }
      }
      if (even_max < odd_min || odd_max < even_min)
        chmax<int>(best_len, aa.size());
    }
    return best_len;
  }
};

//

struct ProblemSolverN2 : public Problem {
private:
  int greedy(int t) {
    // 偶数/奇数要素がt+0.5未満/以上となるように貪欲で選ぶ
    // この貪欲な選び方はtを固定した上では最適
    int best_len = 0;
    repeat(updown, 2) {
      int len = 0;
      bool odd = updown;
      repeat(i, N) {
        if (odd) {
          if (t < A[i]) {
            odd = !odd;
            len += 1;
          }
        } else {
          if (t >= A[i]) {
            odd = !odd;
            len += 1;
          }
        }
      }
      chmax(best_len, len);
    }
    return best_len;
  }

public:
  int solve() override {
    if (N > 6000)
      return -1;

    int best_len = 1;
    repeat(i, N - 1) {
      // 境界値をi+1.5として選ぶ
      // 境界値を元に貪欲に決定
      int l = greedy(i + 1);
      chmax(best_len, l);
    }
    return best_len;
  }
};

//

struct ProblemSolverN2a : public Problem {
  int solve() override {
    if (N > 6000)
      return -1;

    vector<int> vec_down(N); // i+0.5 を境界としている
    vector<int> vec_up(N);

    repeat(i, N) {
      int a = A[i] - 1;
      for (int x = 0; x <= a; ++x) {
        // chmax(vec_up[x], vec_down[x] + 1);
        vec_up[x] = vec_down[x] + 1;
      }
      for (int x = a + 1; x < N; ++x) {
        vec_down[x] = vec_up[x] + 1;
      }
      // 区間のコピーが必要！！
      // 区間の位置が変わらないコピーなので、平方分割が使える。
    }
    int best_len = 1;
    repeat(i, N) chmax(best_len, vec_up[i]);
    repeat(i, N) chmax(best_len, vec_down[i]);
    return best_len;
  }
};

struct ProblemSolverNq : public Problem {
  int solve() override {

    int m = max(3, int(sqrt(N)) + 1);
    SquareRootDecomposition vec_down(m); // i+0.5 を境界としている
    SquareRootDecomposition vec_up(m);
    vec_down.fill(0);
    vec_up.fill(0);

    repeat(i, N) {
      int a = A[i] - 1;
      {
        vec_up.copyValueRange(0, a + 1, vec_down);
        vec_up.addValueRange(0, a + 1, 1);
      }
      {
        vec_down.copyValueRange(a + 1, N, vec_up);
        vec_down.addValueRange(a + 1, N, 1);
      }
    }
    int best_len = 1;
    repeat(i, N) chmax(best_len, vec_up.getValue(i));
    repeat(i, N) chmax(best_len, vec_down.getValue(i));
    return best_len;
  }
};

struct ProblemSolverNl : public Problem {
  int solve() override {

    SegmentTree vec_down(N + 1); // i+0.5 を境界としている
    SegmentTree vec_up(N + 1);
    // vec_down.fill(0);
    // vec_up.fill(0);

    repeat(i, N) {
      int a = A[i] - 1;
      {
        vec_up.copyValueRange(0, a + 1, vec_down);
        vec_up.addValueRange(0, a + 1, 1);
      }
      {
        vec_down.copyValueRange(a + 1, N, vec_up);
        vec_down.addValueRange(a + 1, N, 1);
      }
    }
    int best_len = 1;
    repeat(i, N) chmax(best_len, vec_up.getValue(i));
    repeat(i, N) chmax(best_len, vec_down.getValue(i));
    return best_len;
  }
};

//

//

void test1() {
  Problem p;
  p.N = 8;
  p.A.resize(p.N);
  iota(all(p.A), 1);
  do {

    ProblemSolverExp p1;
    ProblemSolverN2 p2;
    ProblemSolverN2a p3;
    ProblemSolverNq p4;
    ProblemSolverNl p5;
    p1.set(p);
    p2.set(p);
    p3.set(p);
    p4.set(p);
    p5.set(p);

    int a1 = p1.solve();
    int a2 = p2.solve();
    int a3 = p3.solve();
    int a4 = p4.solve();
    int a5 = p5.solve();
    if (a1 != a2 || a2 != a3 || a3 != a4 || a4 != a5) {
      LOG << p.A;
      LOG << a1 << " " << a2 << " " << a3 << " " << a4 << " " << a5;
      break;
    }

  } while (next_permutation(all(p.A)));
  LOG << "done";
}

void test2() {
  Problem p;
  p.N = 100;
  p.A.resize(p.N);
  iota(all(p.A), 1);
  repeat(_, 1000) {
    shuffle(all(p.A), randdev);

    ProblemSolverN2 p2;
    ProblemSolverNl p4;
    p2.set(p);
    p4.set(p);

    int a2 = p2.solve();
    int a4 = p4.solve();
    if (a2 != a4) {
      LOG << p.A;
      LOG << a2 << " " << a4;
      break;
    }
  }
  LOG << "done";
}

void single() {
  // ProblemSolverN2a p;
  // ProblemSolverNq p;
  ProblemSolverNl p;

  int T;
  scanner >> T;
  repeat(i, T) {
    p.scan();
    printer << p.solve() << '\n';
  }
}

int main() {

  single();
  // test2();

  return 0;
}
yukicoder

結果

テストケース

ソースコード
