#902433 (C++17) No.2421 entersys?

提出ソース
結果

問題	No.2421 entersys?
ユーザー	Cyanmond
提出日時	2023-08-12 14:18:29
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	616 ms / 3,000 ms
コード長	21,085 bytes
コンパイル時間	2,764 ms
コンパイル使用メモリ	233,032 KB
実行使用メモリ	39,564 KB
最終ジャッジ日時	2024-11-19 18:28:02
合計ジャッジ時間	12,244 ms
ジャッジサーバーID （参考情報）	judge3 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	4 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	3 ms 5,248 KB
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	3 ms 5,248 KB
testcase_07	AC	3 ms 5,248 KB
testcase_08	AC	3 ms 5,248 KB
testcase_09	AC	4 ms 5,248 KB
testcase_10	AC	3 ms 5,248 KB
testcase_11	AC	425 ms 31,368 KB
testcase_12	AC	427 ms 31,240 KB
testcase_13	AC	433 ms 31,240 KB
testcase_14	AC	432 ms 31,240 KB
testcase_15	AC	442 ms 31,112 KB
testcase_16	AC	447 ms 34,312 KB
testcase_17	AC	459 ms 34,444 KB
testcase_18	AC	448 ms 34,376 KB
testcase_19	AC	453 ms 34,444 KB
testcase_20	AC	467 ms 34,440 KB
testcase_21	AC	391 ms 32,904 KB
testcase_22	AC	325 ms 30,472 KB
testcase_23	AC	616 ms 39,564 KB
testcase_24	AC	566 ms 39,436 KB
testcase_25	AC	585 ms 39,472 KB
testcase_26	AC	252 ms 25,224 KB
testcase_27	AC	239 ms 25,228 KB
testcase_28	AC	253 ms 25,100 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 "main.cpp"
#include <bits/stdc++.h>

#line 2 "template.cpp"

#pragma region templates

#pragma region std::vector operator

template <class T>
std::vector<T> &operator++(std::vector<T> &v) {
    for (auto &e : v) {
        ++e;
    }
    return v;
}

template <class T>
std::vector<T> operator++(std::vector<T> &v, int) {
    auto res = v;
    for (auto &e : v) {
        ++e;
    }
    return res;
}

template <class T>
std::vector<T> &operator--(std::vector<T> &v) {
    for (auto &e : v) {
        --e;
    }
    return v;
}

template <class T>
std::vector<T> operator--(std::vector<T> &v, int) {
    auto res = v;
    for (auto &e : v) {
        --e;
    }
    return res;
}

#pragma endregion

#pragma region ios

namespace scanner {

namespace submodule {
void read(int &a) {
    std::cin >> a;
}

void read(long long &a) {
    std::cin >> a;
}

void read(char &a) {
    std::cin >> a;
}

void read(double &a) {
    std::cin >> a;
}

void read(std::string &a) {
    std::cin >> a;
}

template <class T, class S>
void read(std::pair<T, S> &p) {
    read(p.first);
    read(p.second);
}

template <class T>
void read(std::vector<T> &);

template <class T>
void read(std::vector<T> &a) {
    for (auto &e : a) {
        read(e);
    }
}

template <class T>
void read(T &a) {
    std::cin >> a;
}
} // namespace submodule

void scan() {}

template <class Head, class... Tail>
void scan(Head &head, Tail &...tail) {
    submodule::read(head);
    scan(tail...);
}

void scanI() {}

template <class Head, class... Tail>
void scanI(Head &head, Tail &...tail) {
    submodule::read(head);
    --head;
    scanI(tail...);
}

} // namespace scanner

template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::pair<T, U> pa) {
    os << '{' << pa.first << ", " << pa.second << '}';
    return os;
}

template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> vec) {
    os << "{";
    const int n = (int)vec.size();
    for (int i = 0; i < n; i++) {
        os << vec[i];
        os << (i == n - 1 ? "}" : ", ");
    }
    return os;
}

template <class T, std::size_t S>
std::ostream &operator<<(std::ostream &os, std::array<T, S> arr) {
    os << "{";
    for (int i = 0; i < (int)S; i++) {
        os << arr[i];
        os << (i == S - 1 ? "}" : ", ");
    }
    os << "}";
    return os;
}

template <class T, class U>
std::ostream &operator<<(std::ostream &os, std::map<T, U> ma) {
    os << "{";
    auto itr = ma.begin();
    while (itr != ma.end()) {
        os << *itr << (itr == --ma.end() ? "}" : ", ");
        ++itr;
    }
    return os;
}

template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> st) {
    os << "{";
    auto itr = st.begin();
    while (itr != st.end()) {
        os << *itr << (itr == --st.end() ? "}" : ", ");
        ++itr;
    }
    return os;
}

namespace printer {
void print() {
    std::cout << '\n';
}
template <class Head, class... Tail>
void print(const Head &head, const Tail &...tail) {
    std::cout << head;
    if (sizeof...(tail))
        std::cout << ' ';
    print(tail...);
}

} // namespace printer

namespace dumper {
void dumpFunc() {
    std::cerr << std::endl;
}

template <class Head, class... Tail>
void dumpFunc(Head &&head, Tail &&...tail) {
    std::cerr << head;
    if (sizeof...(Tail) == 0) {
        std::cerr << ' ';
    } else {
        std::cerr << ", ";
    }
    dumpFunc(std::move(tail)...);
}
} // namespace dumper

#pragma endregion

#pragma region functions

template <class T>
constexpr int si(const T &c) {
    return static_cast<int>(c.size());
}

template <class T>
constexpr bool afMin(T &a, const T &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <class T>
constexpr bool afMax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <class T = long long, class S>
constexpr T calcSum(const S &container) {
    return std::accumulate(container.begin(), container.end(), static_cast<T>(0));
}

template <class T>
constexpr auto calcMin(const T &container) {
    return *std::min_element(container.begin(), container.end());
}

template <class T>
constexpr auto calcMax(const T &container) {
    return *std::max_element(container.begin(), container.end());
}

template <class T>
constexpr int lwbi(const T &container, const typename T::value_type &value) {
    return static_cast<int>(std::distance(container.cbegin(), std::lower_bound(container.cbegin(), container.cend(), value)));
}

template <class T>
constexpr int upbi(const T &container, const typename T::value_type &value) {
    return static_cast<int>(std::distance(container.cbegin(), std::upper_bound(container.cbegin(), container.cend(), value)));
}

template <class T>
auto makeVec(const int n, const T &value) {
    return std::vector(n, value);
}

template <class... Args>
auto makeVec(const int n, Args... args) {
    return std::vector(n, makeVec(args...));
}

template <class T, class F>
T binarySearch(T ok, T ng, const F &f) {
    while (abs(ok - ng) > 1) {
        T mid = ok + ng >> 1;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template <class T, class F>
T binarySearchReal(T ok, T ng, const F &f, int iter = 80) {
    while (iter--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

#pragma endregion

#pragma region macros and vars

using namespace scanner;
using namespace printer;
using i64 = long long;

template <class T>
using Vec = std::vector<T>;
template <class T>
using PQ = std::priority_queue<T>;
template <class T>
using RPQ = std::priority_queue<T, std::vector<T>, std::greater<T>>;

std::mt19937 mtRand(std::random_device{}());
constexpr std::array<std::pair<int, int>, 4> dxy4 = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};
constexpr std::array<std::pair<int, int>, 8> dxy8 = {
    {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}};

#define INT(...)                                                                                                       \
    int __VA_ARGS__;                                                                                                   \
    scan(__VA_ARGS__)
#define INTI(...)                                                                                                      \
    int __VA_ARGS__;                                                                                                   \
    scanI(__VA_ARGS__)
#define I64(...)                                                                                                        \
    i64 __VA_ARGS__;                                                                                                    \
    scan(__VA_ARGS__)
#define I64I(...)                                                                                                       \
    i64 __VA_ARGS__;                                                                                                    \
    scanI(__VA_ARGS__)
#define STR(...)                                                                                                       \
    std::string __VA_ARGS__;                                                                                                \
    scan(__VA_ARGS__)
#define CHR(...)                                                                                                       \
    char __VA_ARGS__;                                                                                                  \
    scan(__VA_ARGS__)
#define DOUBLE(...)                                                                                                    \
    double __VA_ARGS__;                                                                                                \
    scan(__VA_ARGS__)
#define VEC(type, name, n)                                                                                             \
    std::vector<type> name(n);                                                                                         \
    scan(name)
#define VECI(type, name, n)                                                                                            \
    std::vector<type> name(n);                                                                                         \
    scanI(name)
#define VEC2(type, name1, name2, n)                                                                                    \
    std::vector<type> name1(n), name2(n);                                                                              \
    for (int i = 0; i < n; i++)                                                                                        \
    scan(name1[i], name2[i])
#define VEC2I(type, name1, name2, n)                                                                                   \
    std::vector<type> name1(n), name2(n);                                                                              \
    for (int i = 0; i < n; i++)                                                                                        \
    scanI(name1[i], name2[i])
#define VEC3(type, name1, name2, name3, n)                                                                             \
    std::vector<type> name1(n), name2(n), name3(n);                                                                    \
    for (int i = 0; i < n; i++)                                                                                        \
    scan(name1[i], name2[i], name3[i])
#define VEC3I(type, name1, name2, name3, n)                                                                            \
    std::vector<type> name1(n), name2(n), name3(n);                                                                    \
    for (int i = 0; i < n; i++)                                                                                        \
    scanI(name1[i], name2[i], name3[i])
#define VEC4(type, name1, name2, name3, name4, n)                                                                      \
    std::vector<type> name1(n), name2(n), name3(n), name4(n);                                                          \
    for (int i = 0; i < n; i++)                                                                                        \
        scan(name1[i], name2[i], name3[i], name4[i]);
#define VEC4I(type, name1, name2, name3, name4, n)                                                                     \
    std::vector<type> name1(n), name2(n), name3(n), name4(n);                                                          \
    for (int i = 0; i < n; i++)                                                                                        \
        scanI(name1[i], name2[i], name3[i], name4[i]);
#define VV(type, name, h, w)                                                                                           \
    std::vector<std::vector<type>> name(h, std::vector<type>(w));                                                      \
    scan(name)
#define VVI(type, name, h, w)                                                                                          \
    std::vector<std::vector<type>> name(h, std::vector<type>(w));                                                      \
    scanI(name)

#define overload5(a, b, c, d, e, name, ...) name
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= (l); --i)
#define fore0(a) rep (a.size())
#define fore1(i, a) for (auto &&i : a)
#define fore2(a, b, v) for (auto &&[a, b] : v)
#define fore3(a, b, c, v) for (auto &&[a, b, c] : v)
#define fore4(a, b, c, d, v) for (auto &&[a, b, c, d] : v)
#define fore(...) overload5(__VA_ARGS__, fore4, fore3, fore2, fore1, fore0)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define mp std::make_pair
#define ALL(x) (x).begin(), (x).end()
#define UNIQUE(x) (x).erase(std::unique((x).begin(), (x).end()), (x).end())
#define fi first
#define se second

#define dump(...)                                                                                                      \
    std::cerr << ' ';                                                                                                  \
    std::cerr << #__VA_ARGS__ << " : [" << __LINE__ << " : " << __FUNCTION__ << "]" << std::endl;                       \
    std::cerr << "    ";                                                                                               \
    dumper::dumpFunc(__VA_ARGS__)

#pragma endregion

#pragma endregion
#line 4 "main.cpp"

#line 1 "/Library/atcoder/lazysegtree.hpp"



#line 8 "/Library/atcoder/lazysegtree.hpp"

#line 1 "/Library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "/Library/atcoder/lazysegtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as F(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "compostiion must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder


#line 6 "main.cpp"

struct MakeIOFast {
    MakeIOFast() {
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        std::cout << std::fixed << std::setprecision(15);
    }
} makeIOFastv;

using namespace std;

int op(int a, int b) {
    return a + b;
}
int e() {
    return 0;
}

int main() {
    INT(N);
    vector<i64> ts;
    vector<string> X(N);
    vector<int> L(N), R(N);
    rep (i, 0, N) {
        scan(X[i], L[i], R[i]);
        ++R[i];
        ts.pb(L[i]);
        ts.pb(R[i]);
    }
    INT(Q);
    vector<int> Type(Q), l(Q), r(Q), t(Q);
    vector<string> x(Q);
    rep (i, 0, Q) {
        scan(Type[i]);
        --Type[i];
        if (Type[i] == 0) {
            scan(x[i], t[i]);
            ts.pb(t[i]);
        }
        if (Type[i] == 1) {
            scan(t[i]);
            ts.pb(t[i]);
        }
        if (Type[i] == 2) {
            scan(x[i], l[i], r[i]);
            ++r[i];
            ts.pb(l[i]);
            ts.pb(r[i]);
        }
    }

    sort(ALL(ts));
    UNIQUE(ts);

    map<string, set<pair<int, int>>> ma;
    const int M = (int)ts.size();
    atcoder::lazy_segtree<int, op, e, int, op, op, e> seg(M);
    rep (i, 0, N) {
        const int li = lwbi(ts, L[i]), ri = lwbi(ts, R[i]);
        seg.apply(li, ri, 1);
        ma[X[i]].insert({L[i], R[i]});
    }
    rep (i, 0, Q) {
        if (Type[i] == 0) {
            auto &u = ma[x[i]];
            auto itr = u.upper_bound({t[i], 1 << 30});
            if (itr == u.begin()) print("No");
            else if ((--itr)->second > t[i]) print("Yes");
            else print("No");
        }
        if (Type[i] == 1) {
            const auto p = lwbi(ts, t[i]);
            print(seg.get(p));
        }
        if (Type[i] == 2) {
            const int li = lwbi(ts, l[i]), ri = lwbi(ts, r[i]);
            seg.apply(li, ri, 1);
            ma[x[i]].insert({l[i], r[i]});
        }
    }
}
yukicoder

結果

テストケース

ソースコード
