Submission #134384

#	Time	Username	Problem	Language	Result	Execution time	Memory
134384		Just_Solve_The_Problem	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	1053 ms	115980 KiB

selling_rna

#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e5 + 7;

int n, m;
string s[N], t[N];
int toint[200];

struct node {
  int to[4];
  int ind, l, r, pr;
  node() {
    l = N;
    r = 0;
    memset(to, -1, sizeof to);
  }
};
node st[(int)2e6 + 7];

int ar[N];

int sz;
int add(string &t, int j) {
  int cur = 0;
  for (int i = 0; i < t.size(); i++) {
    if (st[cur].to[toint[t[i]]] == -1) {
      st[cur].to[toint[t[i]]] = ++sz;
      st[sz].pr = cur;
    }
    cur = st[cur].to[toint[t[i]]];
  }
  reverse(t.begin(), t.end());
  st[cur].ind = lower_bound(s + 1, s + n + 1, t) - s;
  reverse(t.begin(), t.end());
  int temp = cur;
  while (cur) {
    st[cur].r = max(st[cur].r, j);
    st[cur].l = min(st[cur].l, j);
    cur = st[cur].pr;
  }
  return st[temp].ind;
}

int root[N];
struct seg {
  int l, r, val;
  seg() {
    l = r = val = 0;
  }
};
seg tree[N * 30];

void build(int v = 1, int l = 1, int r = n) {
  tree[v].val = 0;
  if (l == r) {
    return ;
  }
  int mid = (l + r) >> 1;
  tree[v].l = ++sz;
  tree[v].r = ++sz;
  build(tree[v].l, l, mid);
  build(tree[v].r, mid + 1, r);
}

void upd(int nv, int ov, int pos, int l = 1, int r = n) {
  tree[nv].val = tree[ov].val;
  if (l == r) {
    tree[nv].val++;
    return ;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) {
    tree[nv].l = ++sz;
    tree[nv].r = tree[ov].r;
    upd(tree[nv].l, tree[ov].l, pos, l, mid);
  } else {
    tree[nv].l = tree[ov].l;
    tree[nv].r = ++sz;
    upd(tree[nv].r, tree[ov].r, pos, mid + 1, r);
  }
  tree[nv].val = tree[tree[nv].l].val + tree[tree[nv].r].val;
}

int get(int nv, int ov, int l, int r, int tl = 1, int tr = n) {
  if (tl > r || tr < l) return 0;
  if (l <= tl && tr <= r) return tree[nv].val - tree[ov].val;
  int mid = (tl + tr) >> 1;
  return get(tree[nv].l, tree[ov].l, l, r, tl, mid) + get(tree[nv].r, tree[ov].r, l, r, mid + 1, tr);
}

main() {
  toint['A'] = 0;
  toint['G'] = 1;
  toint['C'] = 2;
  toint['U'] = 3;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
    t[i] = s[i];
    reverse(t[i].begin(), t[i].end());
  }
  sort(s + 1, s + n + 1);
  sort(t + 1, t + n + 1);
  for (int i = 1; i <= n; i++) {
    ar[i] = add(t[i], i);
  }
  root[0] = 1;
  sz = 0;
  build();
  for (int i = 1; i <= n; i++) {
    root[i] = ++sz;
    upd(root[i], root[i - 1], ar[i]);
  }
  while (m--) {
    string S, T;
    cin >> S >> T;
    int l = lower_bound(s + 1, s + n + 1, S) - s;
    S += '[';
    int r = upper_bound(s + 1, s + n + 1, S) - s - 1;
    if (l > r) {
      puts("0");
      continue;
    }
    reverse(T.begin(), T.end());
    int L, R;
    L = lower_bound(t + 1, t + n + 1, T) - t;
    T += '[';
    R = upper_bound(t + 1, t + n + 1, T) - t - 1;
    if (L > R) {
      puts("0");
      continue;
    }
    //cout << l << ' ' << r << ' ' << L << ' ' << R << endl;
    printf("%d\n", get(root[R], root[L - 1], l, r));
  }
}

Compilation message (stderr)

selling_rna.cpp: In function 'int add(std::__cxx11::string&, int)':
selling_rna.cpp:27:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < t.size(); i++) {
                   ~~^~~~~~~~~~
selling_rna.cpp:28:30: warning: array subscript has type 'char' [-Wchar-subscripts]
     if (st[cur].to[toint[t[i]]] == -1) {
                              ^
selling_rna.cpp:29:28: warning: array subscript has type 'char' [-Wchar-subscripts]
       st[cur].to[toint[t[i]]] = ++sz;
                            ^
selling_rna.cpp:32:32: warning: array subscript has type 'char' [-Wchar-subscripts]
     cur = st[cur].to[toint[t[i]]];
                                ^
selling_rna.cpp: At global scope:
selling_rna.cpp:93:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n, &m);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40