結果

問題 No.2421 entersys?
ユーザー MMMM
提出日時 2023-08-13 21:28:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,712 bytes
コンパイル時間 4,071 ms
コンパイル使用メモリ 256,436 KB
実行使用メモリ 66,264 KB
最終ジャッジ日時 2024-11-21 15:34:21
合計ジャッジ時間 21,804 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 880 ms
51,332 KB
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;

int hsh(string s){
  int res = 0;
  for(auto c : s){
    res *= 30;
    res += c - 'a' + 1;
  }
  return res;
}

int main(){
  // input
  int N; cin >> N;
  set<int> S;
  vector<string> X(N);
  vector<int> H(N),L(N),R(N);
  map<int,set<pair<int,int>>> M;
  for(int i = 0; i < N; i++){
    cin >> X[i] >> L[i] >> R[i];
    S.insert(L[i]);
    S.insert(R[i]);
    H[i] = hsh(X[i]);
    M[H[i]].insert({L[i],R[i]});
  }
  
  // query
  int Q; cin >> Q;
  queue<vector<int>> q;
  while(Q--){
    int op,t,l,r; string x;
    cin >> op;
    if(op == 1){
      cin >> x >> t;
      S.insert(t);
      int h = hsh(x);
      q.push({h,t});
    } else if(op == 2){
      cin >> t;
      q.push({t});
    } else if(op == 3){
      cin >> x >> l >> r;
      S.insert(l);
      S.insert(r);
      int h = hsh(x);
      q.push({h,l,r});
    }
  }
  
  // za-atu
  map<int,int> Z;
  int siz = 0;
  for(auto t : S){
    Z[t] = siz;
    siz++;
  }
  
  // segment tree construction
  fenwick_tree<int> fw(siz+1);
  for(int i = 0; i < N; i++){
    fw.add(Z[L[i]],1);
    fw.add(Z[R[i]]+1,-1);
  }
  
  // answer queries
  while(!q.empty()){
    vector<int> v = q.front(); q.pop();
    if(v.size() == 1)
      cout << fw.sum(0,Z[v[0]]+1) << endl;
    else if(v.size() == 2){
      if(!M.count(v[0])) cout << "No" << endl;
      else{
        auto it = M[v[0]].lower_bound({v[1],2e9});
        it--;
        auto p = *it;
        cout << (p.first <= v[1] && v[1] <= p.second ? "Yes":"No") << endl;
      }
    }
    else if(v.size() == 3){
      M[v[0]].insert({v[1],v[2]});
      fw.add(Z[v[1]],1);
      fw.add(Z[v[2]]+1,-1);
    }
  }
}
0