結果
問題 | No.2421 entersys? |
ユーザー |
|
提出日時 | 2023-08-12 15:23:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 571 ms / 3,000 ms |
コード長 | 6,383 bytes |
コンパイル時間 | 3,265 ms |
コンパイル使用メモリ | 230,596 KB |
最終ジャッジ日時 | 2025-02-16 06:18:07 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/fenwicktree>using namespace std;using ll = long long;using ld = long double;using Pair = pair<int, int>;using Tuple = tuple<int, int, int>;using VI1 = vector<int>;using VI2 = vector<VI1>;using VL1 = vector<ll>;using VL2 = vector<VL1>;using VD1 = vector<ld>;using VD2 = vector<VD1>;using VB1 = vector<bool>;using VB2 = vector<VB1>;using VP1 = vector<Pair>;using VP2 = vector<VP1>;using VT1 = vector<Tuple>;using VT2 = vector<VT1>;using Queue = queue<int>;using DQ = deque<int>;using PQ = priority_queue<int, vector<int>, greater<int>>;using Table = VI2;using Graph = VI2;using FW = atcoder::fenwick_tree<int>;/** io */template <typename T>std::vector<T> input_vec(int N);template <typename T>void output_row(std::vector<T> &row);template <typename T>void output_col(std::vector<T> &col);void outputYesNo(bool yes, const string &Yes = "Yes", const string &No = "No");/** minmax */template <typename T>bool chmin(T &a, T b);template <typename T>bool chmax(T &a, T b);template <typename T>struct CoordinateCompressor {bool compressed;int size_values, size_uniques;vector<T> original_values, uniques;vector<int> compressed_values;CoordinateCompressor(): compressed(false),size_values(0),size_uniques(0),original_values(),uniques(),compressed_values() {}CoordinateCompressor(const vector<T> &original_values): compressed(false),size_values(original_values.size()),size_uniques(0),original_values(original_values),uniques(),compressed_values() {}void add(const T &value) {assert(!compressed);original_values.emplace_back(value);++size_values;compressed = false;}void compress() {if (compressed) return;uniques = original_values;sort(uniques.begin(), uniques.end());uniques.erase(unique(uniques.begin(), uniques.end()), uniques.end());size_uniques = uniques.size();compressed_values.resize(size_values);for (int i = 0; i < size_values; ++i) {auto oi = original_values.at(i);auto it = lower_bound(uniques.begin(), uniques.end(), oi);compressed_values.at(i) = it - uniques.begin();}compressed = true;}const T &at(int i) {if (!compressed) compress();return uniques.at(i);}int operator()(const T &value) {if (!compressed) compress();auto it = lower_bound(uniques.begin(), uniques.end(), value);return it - uniques.begin();}const T &get_original(int i) { return original_values.at(i); }int get_compressed(int i) {if (!compressed) compress();return compressed_values.at(i);}int nunique() {if (!compressed) compress();return size_uniques;}bool has(const T &value) {auto i = operator()(value);if (i == size_uniques) return false;return (uniques.at(i) == value);}};using CCI = CoordinateCompressor<int>;using CCS = CoordinateCompressor<string>;void update(CCI &cci, CCS &ccs, string &Xi, int Li, int Ri,vector<set<Pair>> &member2term, FW &fw) {auto j = ccs(Xi);auto a = cci(Li);auto b = cci(Ri);member2term.at(j).emplace(a, b);fw.add(a, 1);fw.add(b, -1);}auto solve() {int N;cin >> N;vector<string> X(N);VI1 L(N), R(N);for (int i = 0; i < N; ++i) {cin >> X.at(i) >> L.at(i) >> R.at(i);++R.at(i);}int Q;cin >> Q;VI1 type(Q), t(Q), l(Q), r(Q);vector<string> x(Q);for (int i = 0; i < Q; ++i) {cin >> type.at(i);if (type.at(i) == 1) {cin >> x.at(i) >> t.at(i);}if (type.at(i) == 2) {cin >> t.at(i);}if (type.at(i) == 3) {cin >> x.at(i) >> l.at(i) >> r.at(i);++r.at(i);}}CCI cci;CCS ccs;for (int i = 0; i < N; ++i) {ccs.add(X.at(i));cci.add(L.at(i));cci.add(R.at(i));}for (int i = 0; i < Q; ++i) {auto type_i = type.at(i);if (type_i == 1) {ccs.add(x.at(i));cci.add(t.at(i));}if (type_i == 2) {cci.add(t.at(i));}if (type_i == 3) {ccs.add(x.at(i));cci.add(l.at(i));cci.add(r.at(i));}}cci.compress();ccs.compress();int M = ccs.nunique();int T = cci.nunique();vector<set<Pair>> member2term(M);FW fw(T);for (int i = 0; i < N; ++i) {update(cci, ccs, X.at(i), L.at(i), R.at(i), member2term, fw);}for (int i = 0; i < Q; ++i) {auto type_i = type.at(i);if (type_i == 1) {auto j = ccs(x.at(i));auto a = cci(t.at(i));auto &term = member2term.at(j);if (term.empty()) {cout << "No\n";continue;}auto it = term.upper_bound({a, T});if (it == term.begin()) {cout << "No\n";continue;}--it;if (it->first <= a && a < it->second) {cout << "Yes\n";} else {cout << "No\n";}}if (type_i == 2) {auto a = cci(t.at(i));cout << fw.sum(0, a + 1) << "\n";}if (type_i == 3) {update(cci, ccs, x.at(i), l.at(i), r.at(i), member2term, fw);}}}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;// cin >> t;while (t--) {solve();// cout << result << '\n';// output_row(result);// output_col(result);// outputYesNo(result, "Yes", "No");}}/** @note 使用頻度が高く毎回貼付するのが面倒なライブラリを実装しておく。*/template <typename T>std::vector<T> input_vec(int N) {std::vector<T> v(N);for (auto &vi : v) {cin >> vi;}return v;}void outputYesNo(bool yes, const string &Yes, const string &No) {if (yes)cout << Yes << '\n';elsecout << No << '\n';}template <typename T>void output_row(std::vector<T> &row) {int N = row.size();for (int i = 0; i < N; ++i) {if (i > 0) cout << ' ';cout << row.at(i);}cout << '\n';}template <typename T>void output_col(std::vector<T> &col) {int N = col.size();for (int i = 0; i < N; ++i) {cout << col.at(i) << '\n';}}template <typename T>bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}template <typename T>bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}