oj.uz

Submission #134385

# Submission time Handle Problem Language Result Execution time Memory
134385 2019-07-22T14:06:41 Z Just_Solve_The_Problem Selling RNA Strands (JOI16_selling_rna) C++11
100 / 100
 977 ms 49048 KB 
#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));
  }
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 41848 KB Output is correct
2 Correct 38 ms 41848 KB Output is correct
3 Correct 39 ms 41852 KB Output is correct
4 Correct 39 ms 41848 KB Output is correct
5 Correct 39 ms 41848 KB Output is correct
6 Correct 39 ms 41848 KB Output is correct
7 Correct 39 ms 41848 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 46860 KB Output is correct
2 Correct 336 ms 46956 KB Output is correct
3 Correct 311 ms 46684 KB Output is correct
4 Correct 322 ms 47048 KB Output is correct
5 Correct 228 ms 45092 KB Output is correct
6 Correct 232 ms 44920 KB Output is correct
7 Correct 391 ms 45512 KB Output is correct
8 Correct 444 ms 46456 KB Output is correct
9 Correct 440 ms 46424 KB Output is correct
10 Correct 282 ms 46296 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 42448 KB Output is correct
2 Correct 205 ms 42360 KB Output is correct
3 Correct 250 ms 42428 KB Output is correct
4 Correct 213 ms 42264 KB Output is correct
5 Correct 199 ms 42104 KB Output is correct
6 Correct 250 ms 42232 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 41848 KB Output is correct
2 Correct 38 ms 41848 KB Output is correct
3 Correct 39 ms 41852 KB Output is correct
4 Correct 39 ms 41848 KB Output is correct
5 Correct 39 ms 41848 KB Output is correct
6 Correct 39 ms 41848 KB Output is correct
7 Correct 39 ms 41848 KB Output is correct
8 Correct 293 ms 46860 KB Output is correct
9 Correct 336 ms 46956 KB Output is correct
10 Correct 311 ms 46684 KB Output is correct
11 Correct 322 ms 47048 KB Output is correct
12 Correct 228 ms 45092 KB Output is correct
13 Correct 232 ms 44920 KB Output is correct
14 Correct 391 ms 45512 KB Output is correct
15 Correct 444 ms 46456 KB Output is correct
16 Correct 440 ms 46424 KB Output is correct
17 Correct 282 ms 46296 KB Output is correct
18 Correct 282 ms 42448 KB Output is correct
19 Correct 205 ms 42360 KB Output is correct
20 Correct 250 ms 42428 KB Output is correct
21 Correct 213 ms 42264 KB Output is correct
22 Correct 199 ms 42104 KB Output is correct
23 Correct 250 ms 42232 KB Output is correct
24 Correct 411 ms 47172 KB Output is correct
25 Correct 559 ms 47276 KB Output is correct
26 Correct 368 ms 46960 KB Output is correct
27 Correct 413 ms 47100 KB Output is correct
28 Correct 977 ms 49048 KB Output is correct
29 Correct 785 ms 43404 KB Output is correct