結果

問題 No.1788 Same Set
ユーザー pazzle1230
提出日時 2021-12-08 17:23:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,938 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 195,736 KB
最終ジャッジ日時 2025-01-26 06:48:58
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 6 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;
const double eps = 1e-10;
template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
    for(auto &e:u) fill_v<T>(e,v...);
}
template <typename F>
class
#if defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
  [[nodiscard]]
#endif  // defined(__has_cpp_attribute) && __has_cpp_attribute(nodiscard)
FixPoint final : private F
{
public:
  template <typename G>
  explicit constexpr FixPoint(G&& g) noexcept
    : F{std::forward<G>(g)}
  {}
  template <typename... Args>
  constexpr decltype(auto)
  operator()(Args&&... args) const
#if !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 9
  noexcept(noexcept(F::operator()(std::declval<FixPoint>(), std::declval<Args>()...)))
#endif  // !defined(__GNUC__) || defined(__clang__) || __GNUC__ >= 9
  {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};  // class FixPoint
#if defined(__cpp_deduction_guides)
template <typename F>
FixPoint(F&&)
  -> FixPoint<std::decay_t<F>>;
#endif  // defined(__cpp_deduction_guides)
namespace
{
  template <typename F>
#if !defined(__has_cpp_attribute) || !__has_cpp_attribute(nodiscard)
  #  if defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4)
__attribute__((warn_unused_result))
#  elif defined(_MSC_VER) && _MSC_VER >= 1700 && defined(_Check_return_)
_Check_return_
#  endif  // defined(__GNUC__) && (__GNUC__ > 3 || __GNUC__ == 3 && __GNUC_MINOR__ >= 4)
#endif  // !defined(__has_cpp_attribute) || !__has_cpp_attribute(nodiscard)
  inline constexpr decltype(auto)
  makeFixPoint(F&& f) noexcept
  {
    return FixPoint<std::decay_t<F>>{std::forward<std::decay_t<F>>(f)};
  }
}  // namespace
template<class ValueMonoid, class OperatorMonoid, class Modifier,
    template<class...> class Container=::std::vector>
class LazySegTree{
public:
    using value_structure = ValueMonoid;
    using value_type = typename value_structure::value_type;
    using operator_structure = OperatorMonoid;
    using operator_type = typename operator_structure::value_type;
    using modifier = Modifier;
    using const_reference = const value_type &;
    using container_value_type = Container<value_type>;
    using container_operator_type = Container<operator_type>;
    using size_type = typename container_value_type::size_type;
private:
    container_value_type tree;
    container_operator_type lazy;
    size_type size_, height;
    static size_type getsize(const size_type x){
        size_type ret = 1;
        while(ret < x)
            ret <<= 1;
        return ret;
    }
    static size_type getheight(const size_type x){
        size_type ret = 0;
        while((static_cast<size_type>(1) << ret) < x){
            ret++;
        }
        return ret;
    }
    inline static value_type calc(const value_type a, const value_type b){
        return value_structure::operation(a, b);
    }
    inline static void apply(operator_type &data, const operator_type a){
        data = operator_structure::operation(data, a);
    }
    inline static value_type reflect(const value_type v, const operator_type o){
        return modifier::operation(v, o);
    }
    void push(const size_type index){
        tree[index] = reflect(tree[index], lazy[index]);
        apply(lazy[index << 1], lazy[index]);
        apply(lazy[index << 1 | 1], lazy[index]);
        lazy[index] = operator_structure::identity();
    }
    void calc_node(const size_type index){
        if(tree.size() <= (index << 1 | 1)) return;
        assert(0 < index);
        tree[index] = calc(reflect(tree[index << 1],  lazy[index << 1]),
                reflect(tree[index << 1 | 1], lazy[index << 1 | 1]));
    }
    void build(size_type index){
        while(index >>= 1){
            calc_node(index);
        }
    }
    void propagate(const size_type index){
        for(size_type shift = height; shift ; --shift){
            push(index >> shift);
        }
    }
    void rebuild(){
        for(size_type i = size_-1;i > 0;--i){
            calc_node(i);
        }
    }
public:
    LazySegTree() : size_(0), height(0), tree(), lazy(){}
    LazySegTree(const size_type size)
            : size_(size), height(getheight(size)),
                tree(size << 1, value_structure::initializer()),
                lazy(size << 1, operator_structure::identity()){
        rebuild();
    }
    template<class InputIterator>
    LazySegTree(InputIterator first, InputIterator last)
            : size_(::std::distance(first, last)){
        height = getheight(size_);
        tree = container_value_type(size_, value_structure::identity());
        lazy = container_operator_type(size_ << 1, operator_structure::identity());
        tree.insert(tree.end(), first, last);
        rebuild();
    }
    size_type size() const { return size_; }
    const_reference operator[](const size_type k){
        assert(k < size_);
        propagate(k+size_);
        tree[k+size_] = reflect(tree[k+size_], lazy[k+size_]);
        lazy[k+size_] = operator_structure::identity();
        return tree[k+size_];
    }
    value_type query(size_type l, size_type r){
        assert(l <= r);
        assert(0 <= l && l < size_);
        assert(0 <= r && r <= size_);
        value_type retl = value_structure::identity(),
                             retr = value_structure::identity();
        l += size_;
        r += size_;
        propagate(l);
        propagate(r-1);
        build(l);
        build(r-1);
        for(; l < r ; l >>= 1, r >>= 1){
            if(l&1){
                retl = calc(retl, reflect(tree[l], lazy[l]));
                l++;
            }
            if(r&1){
                r--;
                retr = calc(reflect(tree[r], lazy[r]), retr);
            }
        }
        return calc(retl, retr);
    }
    void update(size_type l, size_type r, const operator_type& data){
        assert(l <= r);
        assert(0 <= l && l < size_);
        assert(0 <= r && r <= size_);
        l += size_;
        r += size_;
        propagate(l);
        propagate(r - 1);
        for(size_type l_ = l, r_ = r; l_ < r_ ; l_ >>= 1, r_ >>= 1){
            if(l_ & 1) apply(lazy[l_++], data);
            if(r_ & 1) apply(lazy[--r_], data);
        }
        build(l);
        build(r - 1);
    }
    template<class F>
    void update(size_type index, const F& f){
        assert(0 <= index && index < size());
        index += size_;
        propagate(index);
        tree[index] = f(::std::move(tree[index]));
        lazy[index] = operator_structure::identity();
        build(index);
    }
    /*
    template<class F>
    size_type search(const F& f) const { // [0, result) is True and [0, result-1) is not.
        if(f(value_structure::identity()))
            return 0;
        if(!f(tree[1]))
            return size_+1;
        value_type acc = value_structure::identity();
        size_type i = 1;
        while(i <
    }
    */
};
int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
  int N;
  cin >> N;
  assert(1 <= N && N <= 200000);
  vector<int64> A(N), B(N);
  REP(i, N) {
    cin >> A[i];
    assert(1 <= A[i] && A[i] <= 400000);
  }
  REP(i, N) {
    cin >> B[i];
    assert(1 <= B[i] && B[i] <= 400000);
  }
  int64 res = 0;
  REP(l, N) {
    vector<int64> cntA(400001, 0);
    vector<int64> cntB(400001, 0);
    int cnt_out = 0;
    FOR(r, l, N) {
      if (cntA[A[r]] + cntB[A[r]] != 0 && cntA[A[r]] * cntB[A[r]] == 0) cnt_out--;
      if (cntA[B[r]] + cntB[B[r]] != 0 && cntA[B[r]] * cntB[B[r]] == 0) cnt_out--;
      cntA[A[r]]++;
      cntB[B[r]]++;
      if (cntA[A[r]] + cntB[A[r]] != 0 && cntA[A[r]] * cntB[A[r]] == 0) cnt_out++;
      if (cntA[B[r]] + cntB[B[r]] != 0 && cntA[B[r]] * cntB[B[r]] == 0) cnt_out++;
      if (cnt_out == 0) res++;
    }
  }
  cout << res << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0