제출 #134385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134385		Just_Solve_The_Problem	Selling RNA Strands (JOI16_selling_rna)	C++11	100 / 100	977 ms	49048 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 ar[N];

int sz;
int add(string &t, int j) {
  reverse(t.begin(), t.end());
  int ind = lower_bound(s + 1, s + n + 1, t) - s;
  reverse(t.begin(), t.end());
  return 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() {
  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));
  }
}

컴파일 시 표준 에러 (stderr) 메시지

selling_rna.cpp:66:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:67: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