結果

問題 No.2421 entersys?
ユーザー KudeKude
提出日時 2023-08-12 14:06:28
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 450 ms / 3,000 ms
コード長 2,971 bytes
コンパイル時間 3,439 ms
コンパイル使用メモリ 257,848 KB
実行使用メモリ 33,924 KB
最終ジャッジ日時 2024-11-19 17:22:07
合計ジャッジ時間 11,771 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template <class S>
struct value_compression : vector<S> {
  bool built = false;
  using VS = vector<S>;
  using VS::VS;
  value_compression(vector<S> v) : vector<S>(move(v)) {}
  void build() {
    sort(this->begin(), this->end());
    this->erase(unique(this->begin(), this->end()), this->end());
    built = true;
  }
  template <class T>
  void convert(T first, T last) {
    assert(built);
    for (; first != last; ++first) *first = (*this)(*first);
  }
  int operator()(S x) {
    assert(built);
    return lower_bound(this->begin(), this->end(), x) - this->begin();
  }
  void clear() {
    this->clear();
    built = false;
  }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<tuple<string, int, int>> xlr(n);
  value_compression<string> name2id;
  value_compression<int> vc;
  for(auto& [x, l, r] : xlr) {
    cin >> x >> l >> r, l--;
    name2id.emplace_back(x);
    vc.emplace_back(l);
    vc.emplace_back(r);
  }
  int q;
  cin >> q;
  struct Q {
    int type;
    string x;
    int l, r;
  };
  vector<Q> queries(q);
  for(auto& [type, x, l, r] : queries) {
    cin >> type;
    if (type == 1) {
      cin >> x >> l;
      l--;
      name2id.emplace_back(x);
      vc.emplace_back(l);
    } else if (type == 2) {
      cin >> l;
      l--;
      vc.emplace_back(l);
    } else {
      cin >> x >> l >> r;
      l--;
      name2id.emplace_back(x);
      vc.emplace_back(l);
      vc.emplace_back(r);
    }
  }
  name2id.build();
  vc.build();
  int pcnt = name2id.size();
  int tcnt = vc.size();
  vector<map<int, int>> segs(pcnt);
  fenwick_tree<int> ft(tcnt);
  for(auto& [x, l, r] : xlr) {
    int p = name2id(x);
    l = vc(l);
    r = vc(r);
    segs[p][r] = l;
    ft.add(l, 1);
    ft.add(r, -1);
  }
  for(auto& [type, x, l, r] : queries) {
    if (type == 1) {
      int p = name2id(x);
      l = vc(l);
      auto it = segs[p].upper_bound(l);
      bool ok = it != segs[p].end() && it->second <= l;
      cout << (ok ? "Yes\n" : "No\n");
    } else if (type == 2) {
      l = vc(l);
      cout << ft.sum(0, l + 1) << '\n';
    } else {
      int p = name2id(x);
      l = vc(l);
      r = vc(r);
      segs[p][r] = l;
      ft.add(l, 1);
      ft.add(r, -1);
    }
  }
}
0