fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define db long double
  5. #define vi vector<int>
  6. #define vl vector<ll>
  7. #define vvi vector<vector<int>>
  8. #define vpi vector<pair<int,int>>
  9. #define pb push_back
  10. #define all(v) v.begin(),v.end()
  11. #define rall(v) v.rbegin(),v.rend()
  12. #define sz(v) (int)v.size()
  13. #define fix(n, num) fixed<<setprecision(num)<<n
  14. using namespace std;
  15. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  16. int dy[] = {-1, 1, 0, 0, 1, -1, 1, -1};
  17. const ll N = 1e5 + 5, mod = 1e9 + 7, inf = 1e18;
  18.  
  19. struct node{
  20.     map<char,int>ch;
  21.     int sz=0;
  22.  
  23.     int &operator[](int x){
  24.         return ch[x];
  25.     }
  26. };
  27.  
  28. vector<multiset<int>>ct(N);
  29. struct Trie{
  30.     vector<node>trie;
  31.     void clear(){
  32.         trie.clear();
  33.         trie.emplace_back();
  34.     }
  35.  
  36.     Trie(){ clear(); }
  37.  
  38.     int newNode(){
  39.         trie.emplace_back();
  40.         return sz(trie)-1;
  41.     }
  42.  
  43.     void update(string &s,int op){
  44.         int cur=0;
  45.         for(int i=0;i<sz(s);++i){
  46.             if(trie[cur][s[i]]==0)
  47.                 trie[cur][s[i]]=newNode();
  48.             cur=trie[cur][s[i]];
  49.             auto it= ct[i+1].lower_bound(trie[cur].sz);
  50.             if(it!=ct[i+1].end()&&*it==trie[cur].sz) {
  51.                 ct[i + 1].erase(it);
  52.             }
  53.             trie[cur].sz+=op;
  54.             if(trie[cur].sz) {
  55.                 ct[i + 1].insert(trie[cur].sz);
  56.             }
  57.         }
  58.     }
  59.  
  60.     int query(int l){
  61.         if(sz(ct[l])==0)
  62.             return 0;
  63.         return *(--ct[l].end());
  64.     }
  65.  
  66. };
  67.  
  68. void TC() {
  69.     int q;
  70.     cin>>q;
  71.     vector<int>del(q+1);
  72.     vector<string>s(q+1);
  73.     Trie trie;
  74.     for (int i = 1; i <=q ; ++i) {
  75.         int ty; cin>>ty;
  76.         if(ty==1){
  77.             string st;
  78.             cin>>st;
  79.             reverse(all(st));
  80.             s[i]=st;
  81.             trie.update(st,1);
  82.         }
  83.         else if(ty==2){
  84.             int l,k;
  85.             cin>>k>>l;
  86.             cout<<(trie.query(l)>=k?"YES\n":"NO\n");
  87.         }
  88.         else{
  89.             int x;
  90.             cin>>x;
  91.             if(!del[x]){
  92.                 trie.update(s[x],-1);
  93.                 del[x]=1;
  94.             }
  95.         }
  96.     }
  97.  
  98. }
  99.  
  100. int32_t main() {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(0), cout.tie(0);
  103.  
  104.     int t = 1;
  105.     //  cin >> t;
  106.     for (int i = 1; i <= t; ++i) {
  107.         TC();
  108.     }
  109.  
  110.     return 0;
  111. }
  112.  
Success #stdin #stdout 0.01s 7764KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KfFSFm
language:
C++ (gcc 8.3)
created:
19 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!