제출 #1080023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080023		CDuong	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	1103 ms	129212 KiB

long_mansion

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

template<bool HAS_QUERY, bool HAS_UPDATE, class T, class U, class F1, class F2, class F3>
struct segment_tree_base{
    static_assert(HAS_QUERY || HAS_UPDATE);
#define ifQ if constexpr(HAS_QUERY)
#define ifU if constexpr(HAS_UPDATE)
    int n, size, log;
    vector<T> data;
    vector<U> data_action;
    F1 TT; // monoid operation (always adjacent)
    T T_id; // monoid identity
    F2 UU; // monoid operation (superset, subset)
    U U_id; // monoid identity
    F3 UT; // action of U on T (superset, subset)
    // O(n)
    segment_tree_base(F1 TT, T T_id, F2 UU, U U_id, F3 UT): TT(TT), T_id(T_id), UU(UU), U_id(U_id), UT(UT){ }
    segment_tree_base &operator=(const segment_tree_base &seg){
        n = seg.n;
        size = seg.size;
        log = seg.log;
        data = seg.data;
        data_action = seg.data_action;
    }
    // O(1)
    friend void swap(segment_tree_base &x, segment_tree_base &y){
        swap(x.n, y.n);
        swap(x.size, y.size);
        swap(x.log, y.log);
        swap(x.data, y.data);
        swap(x.data_action, y.data_action);
    }
    // O(n)
    void build(int n){
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        ifQ data.assign(size << 1, T_id);
        ifU data_action.assign(HAS_QUERY ? size : size << 1, U_id);
    }
    // O(n)
    void build(int n, T x){
        static_assert(HAS_QUERY);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        fill(data.begin() + size, data.begin() + size + n, x);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    template<class V>
    void build(const vector<V> &a){
        static_assert(HAS_QUERY);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data.assign(size << 1, T_id);
        copy(a.begin(), a.end(), data.begin() + size);
        for(auto i = size - 1; i >= 1; -- i) refresh(i);
        ifU data_action.assign(size, U_id);
    }
    // O(n)
    void build_action(int n){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        build(n);
    }
    // O(n)
    void build_action(int n, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(n >= 0);
        this->n = n;
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        fill(data_action.begin() + size, data_action.begin() + size + n, f);
    }
    // O(n)
    template<class V>
    void build_action(const vector<V> &a){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        n = (int)a.size();
        size = 1;
        while(size < n) size <<= 1;
        log = __lg(size);
        data_action.assign(size << 1, U_id);
        copy(a.begin(), a.end(), data_action.begin() + size);
    }
    // O(1)
    void refresh(int u){
        static_assert(HAS_QUERY);
        data[u] = TT(data[u << 1], data[u << 1 | 1]);
    }
    // O(1)
    void apply(int u, U f){
        static_assert(HAS_UPDATE);
        ifQ data[u] = UT(f, data[u]);
        if(!HAS_QUERY || u < size) data_action[u] = UU(f, data_action[u]);
    }
    // O(1)
    void push(int u){
        static_assert(HAS_UPDATE);
        apply(u << 1, data_action[u]), apply(u << 1 | 1, data_action[u]);
        data_action[u] = U_id;
    }
    // O(log(n)) if HAS_UPDATE, O(1) otherwise.
    T query(int p){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data[p];
    }
    // O(log(n))
    U query_action(int p){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        return data_action[p];
    }
    // O(log(n))
    T query(int ql, int qr){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return T_id;
        ql += size, qr += size;
        ifU for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        T res_left = T_id, res_right = T_id;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) res_left = TT(res_left, data[ql ++]);
            if(qr & 1) res_right = TT(data[-- qr], res_right);
        }
        return TT(res_left, res_right);
    }
    // O(1)
    T query_all() const{
        static_assert(HAS_QUERY);
        return data[1];
    }
    // O(n)
    vector<T> to_array(){
        static_assert(HAS_QUERY);
        ifU for(auto u = 1; u < size; ++ u) push(u);
        return vector<T>(data.begin() + size, data.begin() + size + n);
    }
    // O(n)
    vector<U> to_array_of_updates(){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        for(auto u = 1; u < size; ++ u) push(u);
        return vector<U>(data_action.begin() + size, data_action.begin() + size + n);
    }
    // O(log(n))
    void set(int p, T x){
        static_assert(HAS_QUERY);
        assert(0 <= p && p < n);
        p += size;
        ifU for(auto i = log; i >= 1; -- i) push(p >> i);
        data[p] = x;
        for(auto i = 1; i <= log; ++ i) refresh(p >> i);
    }
    // O(log(n))
    void set_action(int p, U f){
        static_assert(!HAS_QUERY && HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        data_action[p] = f;
    }
    // O(log(n))
    void update(int p, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= p && p < n);
        p += size;
        for(auto i = log; i >= 1; -- i) push(p >> i);
        ifQ{
            data[p] = UT(f, data[p]);
            for(auto i = 1; i <= log; ++ i) refresh(p >> i);
        }
        else data_action[p] = UU(f, data_action[p]);
    }
    // O(log(n))
    void update(int ql, int qr, U f){
        static_assert(HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) apply(ql ++, f);
            if(qr & 1) apply(-- qr, f);
        }
        ql = _ql, qr = _qr;
        ifQ for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
        static_assert(HAS_QUERY && HAS_UPDATE);
        assert(0 <= ql && ql <= qr && qr <= n);
        if(ql == qr) return;
        ql += size, qr += size;
        for(auto i = log; i >= 1; -- i){
            if(ql >> i << i != ql) push(ql >> i);
            if(qr >> i << i != qr) push(qr >> i);
        }
        auto recurse = [&](auto self, int u)->void{
            if(exit_rule(data[u])) return;
            if(enter_rule(data[u])){
                apply(u, update_rule(data[u]));
                return;
            }
            push(u);
            self(self, u << 1), self(self, u << 1 | 1);
            refresh(u);
        };
        int _ql = ql, _qr = qr;
        for(; ql < qr; ql >>= 1, qr >>= 1){
            if(ql & 1) recurse(recurse, ql ++);
            if(qr & 1) recurse(recurse, -- qr);
        }
        ql = _ql, qr = _qr;
        for(auto i = 1; i <= log; ++ i){
            if(ql >> i << i != ql) refresh(ql >> i);
            if(qr >> i << i != qr) refresh(qr >> i);
        }
    }
    // pred(sum[ql, r)) is T, T, ..., T, F, F, ..., F
    // Returns max r with T
    // O(log(n))
    int max_pref(int ql, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= ql && ql <= n && pred(T_id));
        if(ql == n) return n;
        ql += size;
        ifU for(auto i = log; i >= 1; -- i) push(ql >> i);
        T sum = T_id;
        do{
            while(~ql & 1) ql >>= 1;
            if(!pred(TT(sum, data[ql]))){
                while(ql < size){
                    ifU push(ql);
                    ql = ql << 1;
                    if(pred(TT(sum, data[ql]))) sum = TT(sum, data[ql ++]);
                }
                return ql - size;
            }
            sum = TT(sum, data[ql]);
            ++ ql;
        }while((ql & -ql) != ql);
        return n;
    }
    // pred(sum[l, qr)) is F, F, ..., F, T, T, ..., T
    // Returns min l with T
    // O(log(n))
    int min_suff(int qr, auto pred){
        static_assert(HAS_QUERY);
        assert(0 <= qr && qr <= n && pred(T_id));
        if(qr == 0) return 0;
        qr += size;
        ifU for(auto i = log; i >= 1; -- i) push(qr - 1 >> i);
        T sum = T_id;
        do{
            -- qr;
            while(qr > 1 && qr & 1) qr >>= 1;
            if(!pred(TT(data[qr], sum))){
                while(qr < size){
                    ifU push(qr);
                    qr = qr << 1 | 1;
                    if(pred(TT(data[qr], sum))) sum = TT(data[qr --], sum);
                }
                return qr + 1 - size;
            }
            sum = TT(data[qr], sum);
        }while((qr & -qr) != qr);
        return 0;
    }
    template<class output_stream>
    friend output_stream &operator<<(output_stream &out, segment_tree_base<HAS_QUERY, HAS_UPDATE, T, U, F1, F2, F3> seg){
        out << "{";
        for(auto i = 0; i < seg.n; ++ i){
            ifQ out << seg.query(i);
            else out << seg.query_action(i);
            if(i != seg.n - 1) out << ", ";
        }
        return out << '}';
    }
#undef ifQ
#undef ifU
};

// Supports query
template<class T, class F>
auto make_Q_segment_tree(F TT, T T_id){
    using U = int;
    auto _UU = [&](U, U)->U{ return U{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<true, false, T, U, F, decltype(_UU), decltype(_UT)>(TT, T_id, _UU, U{}, _UT);
}
// Supports update
template<class U, class F>
auto make_U_segment_tree(F UU, U U_id){
    using T = int;
    auto _TT = [&](T, T)->T{ return T{}; };
    auto _UT = [&](U, T)->T{ return T{}; };
    return segment_tree_base<false, true, T, U, decltype(_TT), F, decltype(_UT)>(_TT, T{}, UU, U_id, _UT);
}
// Supports query and update
template<class T, class U, class F1, class F2, class F3>
auto make_QU_segment_tree(F1 TT, T T_id, F2 UU, U U_id, F3 UT){
    return segment_tree_base<true, true, T, U, F1, F2, F3>(TT, T_id, UU, U_id, UT);
}

template<class T, class F>
struct sparse_table{
#ifdef LOCAL
    #define ASSERT(x) assert(x)
#else
    #define ASSERT(x) 42
#endif
    int n;
    vector<vector<T>> data;
    F TT;
    T T_id;
    sparse_table(F TT, T T_id): TT(TT), T_id(T_id){ }
    sparse_table &operator=(const sparse_table &st){
        n = st.n;
        data = st.data;
        return *this;
    }
    friend void swap(sparse_table &stl, sparse_table &str){
        swap(stl.n, str.n);
        swap(stl.data, str.data);
    }
    // O(n * log(n))
    void build(const vector<T> &a){
        n = (int)a.size();
        data.assign({a});
        for(auto p = 1, i = 1; p << 1 <= n; p <<= 1, ++ i){
            data.emplace_back(n - (p << 1) + 1);
            for(auto j = 0; j < (int)data[i].size(); ++ j) data[i][j] = TT(data[i - 1][j], data[i - 1][j + p]);
        }
    }
    // O(1)
    T query(int l, int r) const{
        ASSERT(0 <= l && l <= r && r <= n);
        if(l == r) return T_id;
        int d = __lg(r - l);
        return TT(data[d][l], data[d][r - (1 << d)]);
    }
#undef ASSERT
};
template<class T, class F>
auto make_sparse_table(F TT, T T_id){
    return sparse_table(TT, T_id);
}
template<class T>
auto make_rminq(T inf = numeric_limits<T>::max()){
    return sparse_table([&](const T &x, const T &y){ return min(x, y); }, inf);
}
template<class T>
auto make_rmaxq(T minf = numeric_limits<T>::min()){
    return sparse_table([&](const T &x, const T &y){ return max(x, y); }, minf);
}

struct T1 {
    int l, r;
};

T1 TT(const T1 &A, const T1 &B) {
    return T1{min(A.l, B.l), max(A.r, B.r)};
}

void solve() {
    int n;
    cin >> n;

    vector<int> C(n - 1);
    for (auto &val : C) cin >> val;

    vector<vector<int>> B;
    for (int i = 0; i < n; ++i) {
        int sz; cin >> sz;
        B.emplace_back(sz);
        for (auto &val : B.back()) cin >> val;
    }

    vector<int> en(n);
    vector<int> neededl(n - 1, -1);
    {
        map<int, int> mp;
        for (int i = 0; i < n - 1; ++i) {
            for (auto val : B[i]) mp[val] = i;
            neededl[i] = mp.count(C[i]) ? mp[C[i]] : -1;
        }
        for (int i = n - 1; i >= 0; --i) {
            int cur = i;
            while (cur < n - 1) {
                if (neededl[cur] < i) break;
                cur = en[cur + 1];
            }
            en[i] = cur;
            // cout << i << " " << en[i] << endl;
        }
        // cout << endl;
    }
    vector<int> st(n);
    vector<int> neededr(n - 1, -1);
    {
        map<int, int> mp;
        for (int i = n - 2; i >= 0; --i) {
            for (auto val : B[i + 1]) mp[val] = i + 1;
            neededr[i] = mp.count(C[i]) ? mp[C[i]] : n;
            // cout << i << " " << neededr[i] << endl;
        }
        for (int i = 0; i < n; ++i) {
            int cur = i;
            while (cur > 0) {
                if (neededr[cur - 1] > i) break;
                cur = st[cur - 1];
            }
            st[i] = cur;
            // cout << i << " " << cur << endl;
        }
        // cout << endl;
    }

    auto str = make_Q_segment_tree(TT, T1{n, -1});
    str.build(n);

    auto sptr = make_rmaxq<int>();
    sptr.build(neededr);
    auto sptl = make_rminq<int>();
    sptl.build(neededl);

    for (int i = 0; i < n; ++i) {
        int cl = i, cr = i;
        while (1) {
            int ccl = cl, ccr = cr;
            {
                int lo = 0, hi = cl - 1, opt = cl;
                while (lo <= hi) {
                    int mid = (lo + hi) >> 1;
                    if (sptr.query(mid, cl) <= cr) {
                        opt = mid;
                        hi = mid - 1;
                    }
                    else {
                        lo = mid + 1;
                    }
                }
                auto val = str.query(opt, cl);
                cl = min(cl, val.l), cr = max(cr, val.r);
                // cl = opt;
                // assert(opt == st[i]);
            }
            {
                int lo = cr + 1, hi = n - 1, opt = cr;
                while (lo <= hi) {
                    int mid = (lo + hi) >> 1;
                    if (sptl.query(cr, mid) >= cl) {
                        opt = mid;
                        lo = mid + 1;
                    }
                    else {
                        hi = mid - 1;
                    }
                }
                cr = opt;
                // cout << i << " " << opt << " " << en[i] << endl;
                // assert(opt == en[i]);
            }
            if (ccl == cl and ccr == cr) break;
        }
        // cout << i << " " << cl << " " << cr << endl;

        // int l = 0, r = i - 1, opt = i;
        // while (l <= r) {
        //     int mid = (l + r) >> 1;
        //     if (sptr.query(mid, i) <= en[i]) {
        //         opt = mid;
        //         r = mid - 1;
        //     }
        //     else {
        //         l = mid + 1;
        //     }
        // }
        // cout << i << " " << opt << endl;
        // auto val = st.query(opt, i);
        // val.l = min(val.l, i);
        // val.r = max(val.r, en[i]);
        // cout << i << " " << val.l << " " << val.r << endl;
        str.set(i, T1{cl, cr});
        // cout << endl;
    }

    int q; cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x, --y;

        auto val = str.query(x);
        cout << (min(x, y) >= val.l and max(x, y) <= val.r ? "YES" : "NO") << endl;
    }
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1; //cin >> t;
    while(t--) solve();

#ifdef CDuongg
   auto end = chrono::high_resolution_clock::now();
   cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
   cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
   cout << "Check array size pls sir" << endl;
#endif

}

컴파일 시 표준 에러 (stderr) 메시지

long_mansion.cpp:225:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                       ^~~~
long_mansion.cpp:225:55: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                       ^~~~
long_mansion.cpp:225:72: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  225 |     void update_beats(int ql, int qr, auto exit_rule, auto enter_rule, auto update_rule){
      |                                                                        ^~~~
long_mansion.cpp:258:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  258 |     int max_pref(int ql, auto pred){
      |                          ^~~~
long_mansion.cpp:283:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  283 |     int min_suff(int qr, auto pred){
      |                          ^~~~
long_mansion.cpp: In instantiation of 'T sparse_table<T, F>::query(int, int) const [with T = int; F = make_rmaxq<int>::<lambda(const int&, const int&)>]':
long_mansion.cpp:471:43:   required from here
long_mansion.cpp:346:23: warning: statement has no effect [-Wunused-value]
  346 |     #define ASSERT(x) 42
      |                       ^~
long_mansion.cpp:373:9: note: in expansion of macro 'ASSERT'
  373 |         ASSERT(0 <= l && l <= r && r <= n);
      |         ^~~~~~
long_mansion.cpp: In instantiation of 'T sparse_table<T, F>::query(int, int) const [with T = int; F = make_rminq<int>::<lambda(const int&, const int&)>]':
long_mansion.cpp:488:43:   required from here
long_mansion.cpp:346:23: warning: statement has no effect [-Wunused-value]
  346 |     #define ASSERT(x) 42
      |                       ^~
long_mansion.cpp:373:9: note: in expansion of macro 'ASSERT'
  373 |         ASSERT(0 <= l && l <= r && r <= n);
      |         ^~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75