fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK ""
  5.  
  6. #define ii pair<int, int>
  7.  
  8. struct aho_corasick{
  9.     struct node{
  10.         int suffix_link = -1, exit_link = -1, nxt[128];
  11.         vector<int> leaf;
  12.         node() {fill(nxt, nxt+128, -1);}
  13.     };
  14.     vector<node> g = {node()};
  15.     void insert_string(const string &s, int sidx){
  16.         int p = 0;
  17.         for (char c: s){
  18.             if (g[p].nxt[c] == -1){
  19.                 g[p].nxt[c] = g.size();
  20.                 g.emplace_back();
  21.             }
  22.             p = g[p].nxt[c];
  23.         }
  24.         g[p].leaf.push_back(sidx);
  25.     }
  26.     void build_automaton(){
  27.         for (deque<int> q = {0}; q.size(); q.pop_front()){
  28.             int v = q.front(), suffix_link = g[v].suffix_link;
  29.             if (v) g[v].exit_link = g[suffix_link].leaf.size() ? suffix_link : g[suffix_link].exit_link;
  30.             for (int i=0; i<128; i++){
  31.                 int &nxt = g[v].nxt[i], nxt_sf = v ? g[suffix_link].nxt[i] : 0;
  32.                 if (nxt == -1) nxt = nxt_sf;
  33.                 else{
  34.                     g[nxt].suffix_link = nxt_sf;
  35.                     q.push_back(nxt);
  36.                 }
  37.             }
  38.         }
  39.     }
  40.     vector<int> get_sindex(int p){
  41.         vector<int> a;
  42.         for (int v = g[p].leaf.size() ? p : g[p].exit_link; v != -1; v = g[v].exit_link)
  43.             for (int j: g[v].leaf)
  44.                 a.push_back(j);
  45.         return a;
  46.     }
  47. };
  48.  
  49. struct BIT {
  50.  
  51.     int sz;
  52.     vector<long long> bit;
  53.  
  54.     BIT() {}
  55.     BIT(int _sz) {
  56.         sz = _sz;
  57.         bit.assign(sz + 5, 0);
  58.     }
  59.  
  60.     void update(int id, int x) {
  61.         for (; id <= sz; id += id & (-id)) {
  62.             bit[id] += x;
  63.         }
  64.     }
  65.  
  66.     long long get(int id) {
  67.         long long res = 0LL;
  68.         for (; id > 0; id -= id & (-id)) {
  69.             res += bit[id];
  70.         }
  71.         return res;
  72.     }
  73.  
  74.     long long get(int l, int r) {
  75.         return get(r) - get(l - 1);
  76.     }
  77. };
  78.  
  79. struct Query {
  80.     int qL, qR, id;
  81.  
  82.     long long ans;
  83. };
  84.  
  85. int n, nQ;
  86. string s[102207], t;
  87. int s_size[102207];
  88. vector<int> pos[102207];
  89. int c[102207];
  90. vector<ii> event[102207];
  91. Query qr[102207];
  92.  
  93. int main(){
  94.     ios_base::sync_with_stdio(0);
  95.     cin.tie(0);
  96.  
  97.     if (fopen(TASK".INP", "r")) {
  98.         freopen(TASK".INP", "r", stdin);
  99.         freopen(TASK".OUT", "w", stdout);
  100.     }
  101.  
  102.     cin >> n >> nQ;
  103.  
  104.     aho_corasick ac;
  105.  
  106.     for (int i = 0; i < n; ++i) {
  107.         cin >> s[i] >> c[i];
  108.         ac.insert_string(s[i], i);
  109.         s_size[i] = s[i].size();
  110.     }
  111.     ac.build_automaton();
  112.  
  113.     cin >> t;
  114.     int len = t.length();
  115.  
  116.     for (int i = 0, p = 0; i < len; ++i) {
  117.         p = ac.g[p].nxt[t[i]];
  118.         for (int j : ac.get_sindex(p)) {
  119.             pos[j].push_back(i - s_size[j] + 1);
  120.         }
  121.     }
  122.  
  123.  
  124.     for (int i = 0; i < n; ++i) {
  125.         for (int j = 0; j < (int)pos[i].size(); ++j) {
  126.             int l = pos[i][j] + 1, r = pos[i][j] + s_size[i];
  127.             event[r].push_back(make_pair(l, c[i]));
  128.         }
  129.     }
  130.  
  131.     for (int i = 1; i <= nQ; ++i) {
  132.         cin >> qr[i].qL >> qr[i].qR;
  133.         qr[i].id = i;
  134.     }
  135.  
  136.     sort(qr + 1, qr + nQ + 1, [&](Query q1, Query q2) -> bool{
  137.         return q1.qR < q2.qR;
  138.     });
  139.  
  140.     int x = 0;
  141.     BIT myIT(len);
  142.  
  143.     for (int i = 1; i <= nQ; ++i) {
  144.         while (x < qr[i].qR) {
  145.             ++x;
  146.             for (auto [l, cost] : event[x]) {
  147.                 myIT.update(l, cost);
  148.             }
  149.         }
  150.         qr[i].ans = myIT.get(qr[i].qL, qr[i].qR);
  151.     }
  152.  
  153.     sort(qr + 1, qr + nQ + 1, [&](Query q1, Query q2) -> bool{
  154.         return q1.id < q2.id;
  155.     });
  156.  
  157.     for (int i = 1; i <= nQ; ++i) {
  158.         cout << qr[i].ans << "\n";
  159.     }
  160.  
  161.     return 0;
  162. }
  163.  
Success #stdin #stdout 0.01s 14452KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Wkbs6f
language:
C++14 (gcc 8.3)
created:
20 hours 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!