oj.uz

답안 #668619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
668619 2022-12-04T09:32:07 Z Shin Selling RNA Strands (JOI16_selling_rna) C++17
0 / 100
 132 ms 158412 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

struct fenwick_tree {
  vector<long long> bit;
  int n;
  fenwick_tree(int _n) : n(_n) {
    bit.assign(n + 7, 0);
  }
  long long get(int i) const {
    long long res = 0;
    for (i ++, minimize(i, n); i > 0; i -= i & -i) res += bit[i];
    return res;
  }
  long long get_range(int l, int r) const {
    if (r < l) return 0LL;
    return get(r) - get(l - 1);
  }
  
  void modify(int i, int v) {
    i ++;
    if (i == 0) {
      return;
    }
    for (; i <= n; i += i & -i) bit[i] += v;
  }
};

const char base[] = {'A', 'G', 'C', 'U'};
struct Trie {
  const static int M = 2e6 + 7;
  int node[M][4];
  int num_node;
  int ind[26];
  int cnt[M];
  int tin[M];
  int tout[M];
  Trie() {
    memset(node, 0, sizeof node);
    memset(tin, 0, sizeof tin);
    memset(tout, 0, sizeof tout);
    memset(cnt, 0, sizeof cnt);
    num_node = 0;
    for (int i = 0; i < 4; i ++) {
      ind[base[i] - 'A'] = i;
    }
  }

  int add(string &s) {
    int cur = 0;
    for (int i = 0; i < (int) s.size(); i ++) {
      int c = ind[s[i] - 'A'];
      if (node[cur][c] == 0) {
        node[cur][c] = ++ num_node;
      }
      cur = node[cur][c];
    }
    cnt[cur] ++;
    return cur;
  }

  int find_str(string &s) {
    int cur = 0;
    for (int i = 0; i < (int) s.size(); i ++) {
      int c = ind[s[i] - 'A'];
      if (node[cur][c] == 0) {
        return - 1;
      }
      cur = node[cur][c];
    }
    return cur;
  }

  void dfs_pre(int u = 0) {
    static int timer = 0;
    tin[u] = ++ timer;
    for (int i = 0; i < 4; i ++) if (node[u][i]) {
      dfs_pre(node[u][i]);
    }
    tout[u] = timer;
  }
} pref, suff;

const int N = 2e6 + 7;
int pos[N];
long long rem[N];
long long res[N];
vector<pair<int, int>> qr[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, m; cin >> n >> m;
  for (int i = 1; i <= n; i ++) {
    string s; cin >> s;
    int u = pref.add(s);
    reverse(s.begin(), s.end());
    int v = suff.add(s);
    pos[u] = v;
  }
  pref.dfs_pre();
  suff.dfs_pre();
  for (int i = 1; i <= m; i ++) {
    string p, q; cin >> p >> q;
    reverse(q.begin(), q.end());
    int u = pref.find_str(p);
    int v = suff.find_str(q);
    if (u < 0 || v < 0) {
      continue;
    }
    qr[u].emplace_back(v, i);
  }

  fenwick_tree f(pref.num_node + 7);
  function<void(int)> dfs = [&](int u) {
    for (auto [v, i]: qr[u]) {
      rem[i] = f.get_range(suff.tin[v], suff.tout[v]);
    }
    if (pref.cnt[u]) {
      f.modify(suff.tin[pos[u]], pref.cnt[u]);
    }
    for (int i = 0; i < 4; i ++) if (pref.node[u][i]) {
      dfs(pref.node[u][i]);
    }
    for (auto [v, i]: qr[u]) {
      res[i] = f.get_range(suff.tin[v], suff.tout[v]);
    }
  };

  dfs(0);
  for (int i = 1; i <= m; i ++) {
    cout << res[i] - rem[i] << '\n';
  }
  return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 156860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 132 ms 157372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 158412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 156860 KB Output isn't correct
2 Halted 0 ms 0 KB -