제출 #1290583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290583		nonadhocproblems	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1087 ms	99640 KiB

Main

#include <bit>
#include <bitset>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <cstdio>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <utility>
#include <tuple>
#include <cstdint>
#include <limits>
#include <type_traits>
#include <cmath>
#include <complex>
#include <random>
#include <chrono>
#include <cstring>
#include <cctype>
#include <cassert>
#include <cstdlib>
using namespace std;

#ifdef natural_selection
#include "../../../libra/misc/dbg.h"
#else
#define debug(...)
#define endl "\n"
#endif

const int inf = 1e9;

namespace seg_tree
{
    // Floor of log_2(a); index of highest 1-bit
    inline int floor_log_2(int a)
    {
        return a ? bit_width(unsigned(a)) - 1 : -1;
    }

    class point
    {
    public:
        int a;
        point() : a(0) {}
        explicit point(int a_) : a(a_) { assert(a >= -1); }

        explicit operator bool() { return bool(a); }

        // This is useful so you can directly do array indices
        /* implicit */ operator int() const { return a; }

        point c(bool z) const
        {
            return point((a << 1) | z);
        }

        point operator[](bool z) const
        {
            return c(z);
        }

        point p() const
        {
            return point(a >> 1);
        }

        friend std::ostream &operator<<(std::ostream &o, const point &p) { return o << int(p); }

        template <typename F>
        void for_each(F f) const
        {
            for (int v = a; v > 0; v >>= 1)
            {
                f(point(v));
            }
        }

        template <typename F>
        void for_parents_down(F f) const
        {
            // strictly greater than 0
            for (int L = floor_log_2(a); L > 0; L--)
            {
                f(point(a >> L));
            }
        }

        template <typename F>
        void for_parents_up(F f) const
        {
            for (int v = a >> 1; v > 0; v >>= 1)
            {
                f(point(v));
            }
        }

        point &operator++()
        {
            ++a;
            return *this;
        }
        point operator++(int) { return point(a++); }
        point &operator--()
        {
            --a;
            return *this;
        }
        point operator--(int) { return point(a--); }
    };

    class range
    {
    public:
        int a, b;
        range() : a(1), b(1) {}
        range(int a_, int b_) : a(a_), b(b_)
        {
            assert(1 <= a && a <= b && b <= 2 * a);
        }
        explicit range(std::array<int, 2> r) : range(r[0], r[1]) {}

        explicit operator std::array<int, 2>() const
        {
            return {a, b};
        }

        const int &operator[](bool z) const
        {
            return z ? b : a;
        }

        friend std::ostream &operator<<(std::ostream &o, const range &r) { return o << "[" << r.a << ".." << r.b << ")"; }

        // Iterate over the range from outside-in.
        //   Calls f(point a)
        template <typename F>
        void for_each(F f) const
        {
            for (int x = a, y = b; x < y; x >>= 1, y >>= 1)
            {
                if (x & 1)
                    f(point(x++));
                if (y & 1)
                    f(point(--y));
            }
        }

        // Iterate over the range from outside-in.
        //   Calls f(point a, bool is_right)
        template <typename F>
        void for_each_with_side(F f) const
        {
            for (int x = a, y = b; x < y; x >>= 1, y >>= 1)
            {
                if (x & 1)
                    f(point(x++), false);
                if (y & 1)
                    f(point(--y), true);
            }
        }

        // Iterate over the range from left to right.
        //    Calls f(point)
        template <typename F>
        void for_each_l_to_r(F f) const
        {
            int anc_depth = floor_log_2((a - 1) ^ b);
            int anc_msk = (1 << anc_depth) - 1;
            for (int v = (-a) & anc_msk; v; v &= v - 1)
            {
                int i = countr_zero(unsigned(v));
                f(point(((a - 1) >> i) + 1));
            }
            for (int v = b & anc_msk; v;)
            {
                int i = floor_log_2(v);
                f(point((b >> i) - 1));
                v ^= (1 << i);
            }
        }

        // Iterate over the range from right to left.
        //    Calls f(point)
        template <typename F>
        void for_each_r_to_l(F f) const
        {
            int anc_depth = floor_log_2((a - 1) ^ b);
            int anc_msk = (1 << anc_depth) - 1;
            for (int v = b & anc_msk; v; v &= v - 1)
            {
                int i = countr_zero(unsigned(v));
                f(point((b >> i) - 1));
            }
            for (int v = (-a) & anc_msk; v;)
            {
                int i = floor_log_2(v);
                f(point(((a - 1) >> i) + 1));
                v ^= (1 << i);
            }
        }

        template <typename F>
        void for_parents_down(F f) const
        {
            int x = a, y = b;
            if ((x ^ y) > x)
            {
                x <<= 1, std::swap(x, y);
            }
            int dx = countr_zero(unsigned(x));
            int dy = countr_zero(unsigned(y));
            int anc_depth = floor_log_2((x - 1) ^ y);
            for (int i = floor_log_2(x); i > dx; i--)
            {
                f(point(x >> i));
            }
            for (int i = anc_depth; i > dy; i--)
            {
                f(point(y >> i));
            }
        }

        template <typename F>
        void for_parents_up(F f) const
        {
            int x = a, y = b;
            if ((x ^ y) > x)
            {
                x <<= 1, std::swap(x, y);
            }
            int dx = countr_zero(unsigned(x));
            int dy = countr_zero(unsigned(y));
            int anc_depth = floor_log_2((x - 1) ^ y);
            for (int i = dx + 1; i <= anc_depth; i++)
            {
                f(point(x >> i));
            }
            for (int v = y >> (dy + 1); v; v >>= 1)
            {
                f(point(v));
            }
        }
    };

    class in_order_layout
    {
    public:
        // Alias them in for convenience
        using point = seg_tree::point;
        using range = seg_tree::range;

        int n, s;
        in_order_layout() : n(0), s(0) {}
        in_order_layout(int n_) : n(n_), s(n ? bit_ceil(unsigned(n)) : 0) {}

        point get_point(int a) const
        {
            assert(0 <= a && a < n);
            a += s;
            return point(a >= 2 * n ? a - n : a);
        }

        range get_range(int a, int b) const
        {
            assert(0 <= a && a <= b && b <= n);
            if (n == 0)
                return range();
            a += s, b += s;
            return range((a >= 2 * n ? 2 * (a - n) : a), (b >= 2 * n ? 2 * (b - n) : b));
        }

        range get_range(std::array<int, 2> p) const
        {
            return get_range(p[0], p[1]);
        }

        int get_leaf_index(point pt) const
        {
            int a = int(pt);
            assert(n <= a && a < 2 * n);
            return (a < s ? a + n : a) - s;
        }

        std::array<int, 2> get_node_bounds(point pt) const
        {
            int a = int(pt);
            assert(1 <= a && a < 2 * n);
            int l = countl_zero(unsigned(a)) - countl_zero(unsigned(2 * n - 1));
            int x = a << l, y = (a + 1) << l;
            assert(s <= x && x < y && y <= 2 * s);
            return {(x >= 2 * n ? (x >> 1) + n : x) - s, (y >= 2 * n ? (y >> 1) + n : y) - s};
        }

        int get_node_split(point pt) const
        {
            int a = int(pt);
            assert(1 <= a && a < n);
            int l = countl_zero(unsigned(2 * a + 1)) - countl_zero(unsigned(2 * n - 1));
            int x = (2 * a + 1) << l;
            assert(s <= x && x < 2 * s);
            return (x >= 2 * n ? (x >> 1) + n : x) - s;
        }

        int get_node_size(point pt) const
        {
            auto bounds = get_node_bounds(pt);
            return bounds[1] - bounds[0];
        }
    };

    class circular_layout
    {
    public:
        // Alias them in for convenience
        using point = seg_tree::point;
        using range = seg_tree::range;

        int n;
        circular_layout() : n(0) {}
        circular_layout(int n_) : n(n_) {}

        point get_point(int a) const
        {
            assert(0 <= a && a < n);
            return point(n + a);
        }

        range get_range(int a, int b) const
        {
            assert(0 <= a && a <= b && b <= n);
            if (n == 0)
                return range();
            return range(n + a, n + b);
        }

        range get_range(std::array<int, 2> p) const
        {
            return get_range(p[0], p[1]);
        }

        int get_leaf_index(point pt) const
        {
            int a = int(pt);
            assert(n <= a && a < 2 * n);
            return a - n;
        }

        // Returns {x,y} so that 0 <= x < n and 1 <= y <= n
        // If the point is non-wrapping, then 0 <= x < y <= n
        std::array<int, 2> get_node_bounds(point pt) const
        {
            int a = int(pt);
            assert(1 <= a && a < 2 * n);
            int l = countl_zero(unsigned(a)) - countl_zero(unsigned(2 * n - 1));
            int s = bit_ceil(unsigned(n));
            int x = a << l, y = (a + 1) << l;
            assert(s <= x && x < y && y <= 2 * s);
            return {(x >= 2 * n ? x >> 1 : x) - n, (y > 2 * n ? y >> 1 : y) - n};
        }

        // Returns the split point of the node, such that 1 <= s <= n.
        int get_node_split(point pt) const
        {
            int a = int(pt);
            assert(1 <= a && a < n);
            return get_node_bounds(pt.c(0))[1];
        }

        int get_node_size(point pt) const
        {
            auto bounds = get_node_bounds(pt);
            int r = bounds[1] - bounds[0];
            return r > 0 ? r : r + n;
        }
    };
}

template <typename info, typename tag>
class f_lazy_segment_tree_chan
{
public:
    int n;
    vector<info> infos;
    vector<tag> tags;
    seg_tree::in_order_layout layout;

    void apply(seg_tree::point a, const tag &t)
    {
        auto [l, r] = layout.get_node_bounds(a);
        if (!t.apply_to(infos[a], l, r - 1))     //r - 1 to make inclusive
        {
            assert(a < n);
            downdate_node(a);
            apply(a.c(0), t);
            apply(a.c(1), t);
            update_node(a);
            return;
        }
        if (a < n)
        {
            t.apply_to(tags[a]);
        }
    }

    void downdate_node(seg_tree::point a)
    {
        if (!tags[a].empty())
        {
            apply(a.c(0), tags[a]);
            apply(a.c(1), tags[a]);
            tags[a] = tag();
        }
    }

    void update_node(seg_tree::point a)
    {
        infos[a] = infos[a.c(0)].unite(infos[a.c(1)]);
    }

    f_lazy_segment_tree_chan() : f_lazy_segment_tree_chan(0) {}
    f_lazy_segment_tree_chan(int n_) : f_lazy_segment_tree_chan(vector<info>(n_)) {}
    f_lazy_segment_tree_chan(const vector<info> &a) : n(int(a.size()))
    {
        infos.resize(2 * n);
        tags.resize(n);
        layout = seg_tree::in_order_layout(n);
        for (int i = 0; i < n; i++)
        {
            infos[layout.get_point(i)] = a[i];
        }
        for (int i = n - 1; i >= 1; i--)
        {
            update_node(seg_tree::point(i));
        }
    }

    void modify(int l, int r, const tag &t)
    {
        ++ r;
        auto rng = layout.get_range(l, r);
        rng.for_parents_down([&](seg_tree::point a)
                            { downdate_node(a); });
        rng.for_each([&](seg_tree::point a)
                     { apply(a, t); });
        rng.for_parents_up([&](seg_tree::point a)
                            { update_node(a); });
    }

    void set(int p, const info &v)
    {
        auto pt = layout.get_point(p);
        pt.for_parents_down([&](seg_tree::point a)
                            { downdate_node(a); });
        infos[pt] = v;
        pt.for_parents_up([&](seg_tree::point a)
                          { update_node(a); });
    }

    info query(int l, int r)
    {
        ++ r;
        auto rng = layout.get_range(l, r);
        rng.for_parents_down([&](seg_tree::point a)
                             { downdate_node(a); });
        info res;
        rng.for_each_l_to_r([&](seg_tree::point a)
                            { res = res.unite(infos[a]); });
        return res;
    }

    info get(int p)
    {
        auto pt = layout.get_point(p);
        pt.for_parents_down([&](seg_tree::point a)
                            { downdate_node(a); });
        return infos[pt];
    }

    //returns max point r such that f(sum[l, r]) = true given that f is monotonic as r increases 
    //if (r > n), then f(sum[l, n]) = true 
    //if (r < l), then f(sum[l, l]) = false
    template <typename F>
    int max_right(int l, F f)
    {
        auto rng = layout.get_range(l, n);
        rng.for_parents_down([&](seg_tree::point a) { downdate_node(a); });
        
        int res = n;
        info sum;
        rng.for_each_l_to_r([&](seg_tree::point a)
        {
            if (res != n)
            {
                return;
            }
            auto new_sum = sum.unite(infos[a]);
            if (f(new_sum)) 
            {
                sum = new_sum;
                return;
            }
            while (a < n)
            {
                downdate_node(a);
                new_sum = sum.unite(infos[a.c(0)]);
                if (f(new_sum))
                {
                    sum = new_sum;
                    a = a.c(1);
                } 
                else
                {
                    a = a.c(0);
                }
            }
            res = layout.get_node_bounds(a)[0];
        });
        -- res;
        return min(res, n);
    }

    //returns min point l such that f(sum[l, r]) = true given that f is monotonic as l decreases
    //if (l == 0), then f(sum[0, n]) = true
    //if (l > r), then f(sum[r, r]) = false
    template <typename F>
    int min_left(int r, F f)
    {
        ++ r;
        auto rng = layout.get_range(0, r);
        rng.for_parents_down([&](seg_tree::point a) { downdate_node(a); });
        
        int res = 0;
        info sum;
        rng.for_each_r_to_l([&](seg_tree::point a)
        {
            if (res != 0) 
            {
                return;
            }
            auto new_sum = infos[a].unite(sum);
            if (f(new_sum))
            {
                sum = new_sum;
                return;
            }
            while (a < n)
            {
                downdate_node(a);
                new_sum = infos[a.c(1)].unite(sum);
                if (f(new_sum))
                {
                    sum = new_sum;
                    a = a.c(0);
                }
                else
                {
                    a = a.c(1);
                }
            }
            res = layout.get_node_bounds(a)[1];
        });
        return res;
    }
};

class monoid_chan
{
public:
    int mx = -inf, mn = inf;

    monoid_chan() : mx(-inf), mn(inf) {};
    monoid_chan(int x) : mx(x), mn(x) {};

    monoid_chan unite(monoid_chan b) const 
    {
        monoid_chan res;
        res.mx = max(mx, b.mx);
        res.mn = min(mn, b.mn);
        return res;
    }
    static monoid_chan get_default([[maybe_unused]] int l, [[maybe_unused]] int r)
    {
        return monoid_chan();
    }
};

class tag_chan
{
public:
    int app = -1;

    tag_chan() : app(-1) {};
    tag_chan(int x) : app(x) {};

    bool apply_to(monoid_chan &a, [[maybe_unused]] int l, [[maybe_unused]] int r) const
    {
        assert(app != -1);
        a.mn = a.mx = app;
        return true;
    }
    void apply_to(tag_chan &t) const
    {
        t.app = app;
    }
    bool empty() const
    {
        return app == -1;
    }
};

class monoid_chan2
{
public:
    int val;

    monoid_chan2() : val(0) {};
    monoid_chan2(int x) : val(x) {};

    monoid_chan2 unite(monoid_chan2 b) const 
    {
        monoid_chan2 res(val + b.val);
        return res;
    }
    static monoid_chan2 get_default([[maybe_unused]] int l, [[maybe_unused]] int r)
    {
        return monoid_chan2();
    }
};

class tag_chan2
{
public:
    int add = 0;

    tag_chan2() : add(0) {};
    tag_chan2(int x) : add(x) {};

    bool apply_to(monoid_chan2 &a, [[maybe_unused]] int l, [[maybe_unused]] int r) const
    {
        a.val += add;        
        return true;
    }
    void apply_to(tag_chan2 &t) const
    {
        t.add += add;
    }
    bool empty() const
    {
        return add == 0;
    }
};

/*
class monoid_chan3
{
public:
    int sum = 0;

    monoid_chan3() : sum(0) {};
    monoid_chan3(int x) : sum(x) {};

    monoid_chan3 unite(monoid_chan3 b) const 
    {
        monoid_chan3 res(sum + b.sum);
        return res;
    }
    static monoid_chan3 get_default([[maybe_unused]] int l, [[maybe_unused]] int r)
    {
        return monoid_chan3();
    }
};

class tag_chan3
{
public:
    int add = 0;

    tag_chan3() : add(0) {};
    tag_chan3(int x) : add(x) {};

    bool apply_to(monoid_chan3 &a, [[maybe_unused]] int l, [[maybe_unused]] int r) const
    {
        a.sum += add * (r - l + 1);
        return true;
    }
    void apply_to(tag_chan3 &t) const
    {
        t.add += add;
    }
    bool empty() const
    {
        return add == 0;
    }
};
*/

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for(int i = 1; i <= n; i ++)
            cin >> a[i];
        vector<int> b(n + 1);
        for(int i = 1; i <= n; i ++)
            cin >> b[i];

        int q;
        cin >> q;
        vector<pair<int, int>> qr(q);
        vector<vector<pair<int, int>>> store(n + 1);
        for(int i = 0; i < q; i ++)
        {
            auto &[l, r] = qr[i];
            cin >> l >> r;
            store[r].emplace_back(l, i);
        }

        f_lazy_segment_tree_chan<monoid_chan, tag_chan> cover_l_q(2 * n + 1);
        vector<int> lb(n + 1, 0);
        for(int i = 1; i <= n; i ++)
        {
            int l = b[i], r = a[i];
            lb[i] = cover_l_q.query(l, r).mx;
            lb[i] = max(lb[i], 0);
            cover_l_q.modify(l, r, tag_chan(i));
        }

        f_lazy_segment_tree_chan<monoid_chan, tag_chan> cover_r_q(2 * n + 1);
        vector<int> rb(n + 1, n + 1);
        for(int i = n; i >= 1; i --)
        {
            int l = b[i], r = a[i];
            rb[i] = cover_r_q.query(l, r).mn;
            rb[i] = min(rb[i], n + 1);
            cover_r_q.modify(l, r, tag_chan(i));
        }
        
        vector<bool> ans(q, false);

        vector<vector<int>> rem(n + 2);
        f_lazy_segment_tree_chan<monoid_chan2, tag_chan2> ban_q(n + 1);
        for(int i = 1; i <= n; i ++)
        {
            for(auto j : rem[i])
                ban_q.modify(lb[j] + 1, j, tag_chan2(-1));

            ban_q.modify(lb[i] + 1, i, tag_chan2(+1));
            rem[rb[i]].push_back(i);

            for(auto [l, idx] : store[i])
                ans[idx] = (ban_q.get(l).val == 0); 
        }

        for(int i = 0; i < q; i ++)
            cout << (ans[i] ? "Yes" : "No") << endl;
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 8 / 8
• Subtask 6: 12 / 12
• Subtask 7: 18 / 18
• Subtask 8: 12 / 12