結果

問題 No.127 門松もどき
ユーザー OrisanoOrisano
提出日時 2016-02-26 02:33:45
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 4,874 bytes
コンパイル時間 1,568 ms
コンパイル使用メモリ 175,932 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-22 13:51:30
合計ジャッジ時間 2,480 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
6,816 KB
testcase_01 AC 4 ms
6,940 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 WA -
testcase_05 AC 3 ms
6,940 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h> // {{{

#define GET_MACRO(a, b, c, d, NAME, ...) NAME
#define REP(...) GET_MACRO(__VA_ARGS__, REP4, REP3, REP2)(__VA_ARGS__)
#define REP2(i, a) REP3(i, 0, a)
#define REP3(i, a, b) REP4(i, a, b, 1)
#define REP4(i, a, b, s) for (int i = (a); i < (int)(b); i += (s))
#define REPR(...) GET_MACRO(__VA_ARGS__, REPR4, REPR3, REPR2)(__VA_ARGS__)
#define REPR2(i, a) REPR3(i, 0, a)
#define REPR3(i, a, b) REPR4(i, a, b, 1)
#define REPR4(i, a, b, s) for (int i = (b)-1; i >= (int)(a); i -= (s))
#define ALL(c) (c).begin(), (c).end()
#define DUMP(x) (std::cerr << #x << ':' << ' ' << x << '\n')
#define TMPL_T template <typename T>
#define TMPL_TU template <typename T, typename U>
#define mut auto
#define let const auto

using Int = long long;
// clang-format off
namespace extio {
std::string delimiter=" ",pdelimiter=" ";
std::string bracket_b="",bracket_e="";
void chdelim(const std::string&s){delimiter=s;}
void chpdelim(const std::string&s){pdelimiter=s;}
void chbracket(const std::string&b,const std::string&e){bracket_b=b,bracket_e=e;}
TMPL_T  void pcont(std::ostream&os,const T&x){int c=0;for(const auto&a:x){if(c++)os<<delimiter;os<<a;}}
TMPL_TU void ppair(std::ostream&os,const std::pair<T,U>&p){os<<bracket_b<<p.first<<pdelimiter<<p.second<<bracket_e;}
}
namespace std {
TMPL_T ostream& operator<<(ostream&os,const vector<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const set<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const multiset<T>&x){extio::pcont(os,x);return os;}
TMPL_T ostream& operator<<(ostream&os,const deque<T>&x){extio::pcont(os,x);return os;}
TMPL_TU ostream& operator<<(ostream&os,const map<T,U>&x){extio::pcont(os,x);return os;}
TMPL_TU ostream& operator<<(ostream&os,const pair<T,U>&x){extio::ppair(os,x);return os;}
}
TMPL_TU inline bool chmax(T&x,U a){return x<a&&(x=a,1);}
TMPL_TU inline bool chmin(T&x,U a){return a<x&&(x=a,1);}

inline int in(){int x;std::cin>>x;return x;}

struct Initializer_ {
  Initializer_(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(0);
    std::cout << std::setprecision(10);
    std::cerr << std::setprecision(10);
  }
} precalc;
// clang-format on
// }}}

//{{{ seg.hpp
#ifndef INCLUDE_SEG_HPP
#define INCLUDE_SEG_HPP

#include <cstdint>
#include <algorithm>
#include <utility>

namespace orliv {
namespace seg {
constexpr std::uint64_t upperPow2(std::uint64_t x, std::uint64_t r = 1) {
  return x <= r ? r : upperPow2(x, r + r);
}

template <typename T>
struct Max {
  using value_type = T;
  static const value_type default_value = 0;
  static value_type merge(const value_type &a, const value_type &b) {
    return std::max(a, b);
  }
  static value_type eval(std::int64_t L, std::int64_t R, value_type v,
                         value_type lazy) {
    return v + lazy;
  }
};
}
}
#endif
//}}}
//{{{ seg_tree.hpp
#ifndef INCLUDE_SEG_TREE_HPP
#define INCLUDE_SEG_TREE_HPP

#ifndef INCLUDE_SEG_HPP
#include "seg.hpp"
#endif

#include <algorithm>
#include <vector>
#include <cassert>

namespace orliv {
namespace ds {
template <typename SegTraits, int S>
struct SegTree {
  using seg_t = typename SegTraits::value_type;
  static constexpr int N = seg::upperPow2(S);
  seg_t data[N * 2];
  SegTree(seg_t init = SegTraits::default_value)
      : SegTree(std::vector<seg_t>(N, init), init) {}
  SegTree(const std::vector<seg_t> &V, seg_t init = SegTraits::default_value) {
    assert(V.size() <= N);
    for (int i = 0; i < V.size(); i++)
      data[i + N - 1] = V[i];
    for (int i = V.size(); i < N; i++)
      data[i + N - 1] = init;
    for (int i = N - 2; i >= 0; --i) {
      data[i] = SegTraits::merge(data[i + i + 1], data[i + i + 2]);
    }
  }
  void update(int x, seg_t v) {
    x += N - 1;
    data[x] = v;
    while (x) {
      x = (x - 1) >> 1;
      data[x] = SegTraits::merge(data[x + x + 1], data[x + x + 2]);
    }
  }
  void add(int x, seg_t a) { update(x, data[x + N - 1] + a); }
  seg_t query(int a = 0, int b = N, int x = 0, int l = 0, int r = N) const {
    if (r <= a || b <= l) return SegTraits::default_value;
    if (a <= l && r <= b) return data[x];
    return SegTraits::merge(query(a, b, x + x + 1, l, (l + r) >> 1),
                            query(a, b, x + x + 2, (l + r) >> 1, r));
  }
};
}
}
#endif
//}}}

using namespace std;

signed main() {
  using max_seg = orliv::ds::SegTree<orliv::seg::Max<int>, 3000>;
  max_seg L(0), R(0);

  const int MA = 100100;
  vector<vector<int>> bkt(MA);

  int N = in();
  REP(i, N) { bkt[in()].emplace_back(i); }
  REP(v, MA) {
    vector<pair<int, int>> update;
    for (int idx : bkt[v]) {
      update.emplace_back(L.query(0, idx), R.query(idx, N));
    }
    REP(i, bkt[v].size()) {
      L.update(bkt[v][i], update[i].second + 1);
      R.update(bkt[v][i], update[i].first + 1);
    }
  }
  cout << max(L.query(), R.query()) << endl;
  return 0;
}
0