結果
| 問題 |
No.2421 entersys?
|
| コンテスト | |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2023-08-12 14:18:29 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 745 ms / 3,000 ms |
| コード長 | 21,085 bytes |
| コンパイル時間 | 3,659 ms |
| コンパイル使用メモリ | 223,120 KB |
| 最終ジャッジ日時 | 2025-02-16 04:33:16 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 28 |
ソースコード
#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]});
}
}
}