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

提出ソース

結果

問題	No.2421 entersys?
ユーザー	dokaraya
提出日時	2023-08-12 15:22:09
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	7,028 bytes
コンパイル時間	3,434 ms
コンパイル使用メモリ	236,948 KB
実行使用メモリ	813,840 KB
最終ジャッジ日時	2024-04-30 09:01:05
合計ジャッジ時間	6,315 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	3 ms 6,944 KB
testcase_02	AC	7 ms 6,940 KB
testcase_03	AC	3 ms 6,944 KB
testcase_04	AC	4 ms 6,940 KB
testcase_05	AC	7 ms 6,944 KB
testcase_06	AC	6 ms 6,940 KB
testcase_07	AC	7 ms 6,944 KB
testcase_08	AC	8 ms 7,552 KB
testcase_09	AC	10 ms 8,448 KB
testcase_10	AC	6 ms 6,940 KB
testcase_11	MLE	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "template.hpp"
#include<bits/stdc++.h>
using ll = long long;
#define REP(i, n) for(ll i = 0; (i) < ll(n); ++ (i))
#define FOR(i, m, n) for(ll i = (m); (i) <= ll(n); ++ (i))
#define REPR(i, n) for(ll i = ll(n) - 1; (i) >= 0; -- (i))
#define FORR(i, m, n) for(ll i = ll(n); (i) >= ll(m); -- (i))
#define ALL(x) x.begin(),x.end()

#define INF (int)1e9
#define LLINF (long long)1e18
#define MOD (int)(1e9+7)
#define MOD9 (int)998244353
#define PI 3.141592653589
#define PB push_back
#define F first
#define S second

#define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;}
#define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define Yes(T) {cout<<"Yes"<<endl; if(T) return 0;}
#define No(T) {cout <<"No"<<endl; if(T) return 0;}
#define YES(T) {cout<<"YES"<<endl; if(T) return 0;}
#define NO(T) {cout <<"NO"<<endl; if(T) return 0;}

#define Graph vector<vector<int> >
#define CostGraph vector<vector<pair<int,ll> > >
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define VI vector<int>
#define VL vector<ll>
#define VVI vector<vector<int> >
#define VVL vector<vector<ll> >
#define VPII vector<pair<int,int> >
#define VPLL vector<pair<ll,ll> >

#define DDD fixed<<setprecision(10)
#define PAD setfill('0')<<right<<setw(8)

template <class T>
inline bool chmin(T &a, T b) {
  if(a > b){ a = b; return true;}
  return false;
}
template <class T>
inline bool chmax(T &a, T b) {
  if(a < b){a = b; return true;}
  return false;
}
struct input{
  int n;
  input() {}
  input(int n_) : n(n_){};
  template <class T>
  operator T(){
    T ret;
    std::cin >> ret;
    return ret;
  }
  template <class T>
  operator std::vector<T>() {
    std::vector<T> ret(n);
    REP(i,n) std::cin >> ret[i];
    return ret;
  }
};
template <class T>
inline void printVec(std::vector<T> v){
  REP(i,v.size()){
    if(i) std::cout << " ";
    std::cout << v[i];
  } std::cout << std::endl;
}

using namespace std;
#line 1 "data-structure/segment-tree/segment-tree.hpp"
template <typename T>
struct SegmentTree{
  using F = function<T(T, T)>;
  int sz;
  vector<T> seg;

  const F f;
  const T e;

  SegmentTree(int n, const F f, const T &e): f(f), e(e){
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, e);
  }

  void set(int k, const T &x){
    seg[k+sz] = x;
  }

  void build(){
    for(int k = sz - 1; k > 0; --k){
      seg[k] = f(seg[2*k+0], seg[2*k+1]);
    }
  }

  void update(int k, const T &x){
    k += sz;
    seg[k] = x;
    while(k >>= 1){
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  T query(int a, int b){
    T l = e, r = e;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
      if(a & 1) l = f(l, seg[a++]);
      if(b & 1) r = f(seg[--b], r);
    }
    return f(l, r);
  }

  T operator[](const int &k) const{
    return seg[k + sz];
  }

  template <typename C>
  int findSubtree(int a, const C &check, T &m, bool type){
    while(a < sz){
      T nxt = type ? f(seg[2 * a + type], m): f(m, seg[2 * a + type]);
      if(check(nxt)) a = 2 * a + type;
      else m = nxt, a = 2 * a + 1 - type;
    }
    return a - sz;
  }

  template<typename C>
  int findFirst(int a, const C &check){
    T l = e;
    if(a <= 0){
      if(check(f(l, seg[1]))) return findSubtree(1, check, l, false);
      return -1;
    }
    int b = sz;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1){
      if(a & 1) {
        T nxt = f(l, seg[a]);
        if(check(nxt)) return findSubtree(a, check, l, false);
        l = nxt;
        ++a;
      }
    }
    return -1;
  }

  template <typename C>
  int findLast(int b, const C &check){
    T r = e;
    if(b >= sz) {
      if(check(f(seg[1], r))) return findSubtree(1, check, r, true);
      return -1;
    }
    int a = sz;
    for(b += sz; a < b; a >>= 1, b >>= 1){
      if(b & 1){
        T nxt = f(seg[--b], r);
        if(check(nxt)) return findSubtree(b, check, r, true);
        r = nxt;
      }
    }
    return -1;
  }
};
#line 2 "data-structure/segment-tree/range-sum-query.hpp"
struct RangeSumQuery{
  int n;
  SegmentTree<short> seg;
  RangeSumQuery(int n): n(n), seg(n, [&](short l, short r){
    return l + r;
  }, 0){

  }

  void update(int k, int val){
    seg.update(k, val);
  }

  void add(int k, int val){
    seg.update(k, seg.query(k, k+1) + val);
  }

  short query(int l, int r){
    return seg.query(l, r);
  }
};
#line 3 "main.cpp"

template<typename T>
struct Compress{
  vector<T> xs;

  Compress() = default;

  Compress(const vector<T> &vs){
    add(vs);
  }

  Compress(const initializer_list<vector<T>> &vs) {
    for(auto &p :vs) add(p);
  }

  void add(const vector<T> &vs) {
    copy(begin(vs), end(vs), back_inserter(xs));
  }

  void add(const T &x) {
    xs.emplace_back(x);
  }

  void build() {
    sort(ALL(xs));
    xs.erase(unique(ALL(xs)), end(xs));
  }

  vector<int> get(const vector<T> &vs) const{
    vector<int> ret;
    transform(ALL(vs), back_inserter(ret), [&](const T &x) {
      return lower_bound(ALL(xs), x) - begin(xs);
    });
    return ret;
  }

  int get(const T &x) const{
    return lower_bound(ALL(xs), x) - begin(xs);
  }

  const T &operator[](int k) const {
    return xs[k];
  }
};

int main(){
  int n;
  cin >> n;
  VI cmp;
  map<string, int> xId;
  vector<string> x(n);
  VI l(n), r(n);
  REP(i, n) {
    cin >> x[i] >> l[i] >> r[i];
    cmp.PB(l[i]);
    cmp.PB(r[i]);
  }
  int q;
  cin >> q;
  vector<pair<string, VI>> query(q);
  REP(i,q){
    int t;
    cin >> t;
    pair<string,VI> item;
    item.second.PB(t);
    if(t == 1){
      cin >> item.first;
      if(!xId.count(item.first)) xId[item.first] = xId.size();
      int p;
      cin >> p;
      item.second.PB(p);
      cmp.PB(p);
    }else if(t == 2){
      int p;
      cin >> p;
      item.second.PB(p);
      cmp.PB(p);
    }else{
      cin >> item.first;
      int l, r;
      cin >> l >> r;
      item.second.PB(l);
      item.second.PB(r);
      cmp.PB(l);
      cmp.PB(r);
    }
    query[i] = item;
  }
  sort(ALL(cmp));
  Compress<int> comp(cmp);
  comp.build();

  RangeSumQuery rsq(comp.xs.size()+1);
  vector<RangeSumQuery> vrsq(xId.size(), RangeSumQuery(comp.xs.size()+1));
  REP(i,n){
    rsq.add(comp.get(l[i]), 1);
    rsq.add(comp.get(r[i])+1, -1);
    if(xId.count(x[i])){
      vrsq[xId[x[i]]].add(comp.get(l[i]), 1);
      vrsq[xId[x[i]]].add(comp.get(r[i])+1, -1);
    }
  }

  REP(i,q){
    int t = query[i].second[0];
    if(t == 1){
      string xp = query[i].first;
      int p = query[i].second[1];
      cout << (vrsq[xId[xp]].query(0, comp.get(p)+1) >= 1? "Yes" : "No") << endl;
    }else if(t == 2){
      int p = query[i].second[1];
      cout << rsq.query(0, comp.get(p)+1) << endl;
    }else{
      string xp = query[i].first;
      int lp = query[i].second[1];
      int rp = query[i].second[2];
      rsq.add(comp.get(lp), 1);
      rsq.add(comp.get(rp)+1, -1);
      if(xId.count(xp)){
        vrsq[xId[xp]].add(comp.get(lp), 1);
        vrsq[xId[xp]].add(comp.get(rp)+1, -1);
      }
    }
  }
}

yukicoder

結果

テストケース

ソースコード