fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define int long long
  4.  
  5. using namespace std;
  6.  
  7. const int N = 2e5;
  8. int n, q;
  9. string a[N + 1];
  10.  
  11. struct query {
  12.     int k, l;
  13.     vector<int> g;
  14. } Q[N + 1];
  15.  
  16. struct trie {
  17.     vector<array<int, 26>> T;
  18.     vector<int> val;
  19.     trie(): T(1), val(1) {}
  20.  
  21.     int add(string &s, int x, int e) {
  22.         int u = 0, cnt = 0;
  23.         for (int c : s) {
  24.             c -= 'a';
  25.             if (!T[u][c])
  26.                 T[u][c] = T.size(),
  27.                 T.emplace_back(),
  28.                 val.emplace_back();
  29.  
  30.             u = T[u][c];
  31.             cnt -= val[u] == e;
  32.             val[u] += x;
  33.             cnt += val[u] == e;
  34.         }
  35.         return cnt;
  36.     }
  37. };
  38.  
  39. trie T;
  40.  
  41. namespace sub14 {
  42.     bool detect() {
  43.         return true;
  44.     }
  45.  
  46.     void main() {
  47.         for (int i = 0; i < q; ++i) {
  48.             auto [k, l, g] = Q[i];
  49.             int ans = 0;
  50.             for (int j : g)
  51.                 ans += T.add(a[j], 1, l);
  52.             cout << ans << '\n';
  53.             for (int j : g)
  54.                 T.add(a[j], -1, l);
  55.         }
  56.     }
  57. }
  58.  
  59. int32_t main() {
  60.     ios::sync_with_stdio(0), cin.tie(0);
  61.  
  62.     #define _ "purple"
  63.     if (fopen(_ ".inp", "r")) {
  64.         freopen(_ ".inp", "r", stdin);
  65.         freopen(_ ".out", "w", stdout);
  66.     }
  67.  
  68.     cin >> n >> q;
  69.     for (int i = 1; i <= n; ++i) cin >> a[i];
  70.     for (int i = 0; i < q; ++i) {
  71.         cin >> Q[i].k >> Q[i].l;
  72.         Q[i].g.resize(Q[i].k);
  73.  
  74.         for (int &j : Q[i].g) cin >> j;
  75.     }
  76.  
  77.     if (sub14::detect()) sub14::main();
  78. }
  79.  
Success #stdin #stdout 0.01s 17672KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ItaJBZ
language:
C++14 (gcc 8.3)
created:
1 day 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!