oj.uz

Submission #243942

# Submission time Handle Problem Language Result Execution time Memory
243942 2020-07-02T09:47:45 Z fedoseevtimofey Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 162 ms 79512 KB 
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int L = 4e6 + 7;

string rev(string s) {
  reverse(s.begin(), s.end());
  return s;
} 

int get_id(char c) {
  if (c == 'A') {
    return 0;
  } else if (c == 'G') {
    return 1;
  } else if (c == 'C') {
    return 2;
  } else {
    return 3;
  }
}

int go[L][4];
int l[L], r[L];

int uk = 2;

int add(string s, int rt) {
  int v = rt;
  for (char c : s) {
    int id = get_id(c);
    if (go[v][id] == 0) {
      go[v][id] = uk++;
    }
    v = go[v][id];
  }
  return v;
}

int find_string(string s, int rt) {
  int v = rt;
  for (char c : s) {
    int id = get_id(c);
    if (go[v][id] == 0) return -1;
    v = go[v][id];
  }
  return v;
}

vector <int> e;

void dfs(int u) {
  e.push_back(u);
  l[u] = (int)e.size() - 1;
  for (int i = 0; i < 4; ++i) {
    if (go[u][i] != 0) {
      dfs(go[u][i]);
    }
  }
  r[u] = (int)e.size() - 1;
}

struct Fenwick {
  vector <int> f;
  int n;
  Fenwick(int nn) {
    n = nn;
    f.resize(n);
  }
  void modify(int i, int val) {
    for (; i < n; i |= i + 1) {
      f[i] += val;
    }
  }

  int get(int r) {
    int res = 0;
    for (; r >= 0; r &= r + 1, --r) {
      res += f[r];
    }
    return res;
  }

  int sum(int l, int r) {
    return get(r) - get(l - 1);
  }
};

struct Event {
  int x, l, r, tp, id;
  Event(int x, int l, int r, int tp, int id) : x(x), l(l), r(r), tp(tp), id(id) {}
  bool operator <(const Event &other) const {
    if (x != other.x) return x < other.x;
    return id < other.id;
  }
};    

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, m;
  cin >> n >> m;
  int rt1 = 0, rt2 = 1;
  vector <vector <int>> where(2, vector <int> (n));
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    where[0][i] = add(s, rt1);
    where[1][i] = add(rev(s), rt2);
  }

  dfs(rt1); 
  e.clear();
  dfs(rt2);
  vector <Event> events;
  for (int i = 0; i < n; ++i) {
    events.emplace_back(l[where[0][i]], l[where[1][i]], -1, -1, -1);
  }
  vector <int> ans(m); 
  for (int i = 0; i < m; ++i) {
    string p, q;
    cin >> p >> q;
    q = rev(q);
    int s1 = find_string(p, rt1), s2 = find_string(q, rt2);
    if (s1 == -1 || s2 == -1) {
      continue;
    }
    events.emplace_back(r[s1], l[s2], r[s2], 1, i);
    events.emplace_back(l[s1] - 1, l[s2], r[s2], -1, i);
  } 
  sort(events.begin(), events.end());
  Fenwick F(L);
  for (auto e : events) {
    if (e.id == -1) {
      F.modify(e.l, 1);
    } else {
      ans[e.id] += e.tp * F.sum(e.l, e.r);
    }   
  } 
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << '\n';
  }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16000 KB Output is correct
2 Correct 13 ms 16000 KB Output is correct
3 Correct 13 ms 16128 KB Output is correct
4 Correct 13 ms 16000 KB Output is correct
5 Correct 13 ms 16128 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 14 ms 16000 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 70756 KB Output is correct
2 Correct 116 ms 67896 KB Output is correct
3 Correct 121 ms 70152 KB Output is correct
4 Correct 112 ms 67536 KB Output is correct
5 Correct 158 ms 78544 KB Output is correct
6 Correct 162 ms 79512 KB Output is correct
7 Correct 52 ms 16588 KB Output is correct
8 Correct 103 ms 53084 KB Output is correct
9 Correct 98 ms 47196 KB Output is correct
10 Correct 80 ms 46308 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 19996 KB Output is correct
2 Correct 43 ms 18864 KB Output is correct
3 Correct 52 ms 19560 KB Output is correct
4 Correct 45 ms 18912 KB Output is correct
5 Correct 42 ms 18824 KB Output is correct
6 Correct 52 ms 19560 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16000 KB Output is correct
2 Correct 13 ms 16000 KB Output is correct
3 Correct 13 ms 16128 KB Output is correct
4 Correct 13 ms 16000 KB Output is correct
5 Correct 13 ms 16128 KB Output is correct
6 Correct 13 ms 16000 KB Output is correct
7 Correct 14 ms 16000 KB Output is correct
8 Correct 118 ms 70756 KB Output is correct
9 Correct 116 ms 67896 KB Output is correct
10 Correct 121 ms 70152 KB Output is correct
11 Correct 112 ms 67536 KB Output is correct
12 Correct 158 ms 78544 KB Output is correct
13 Correct 162 ms 79512 KB Output is correct
14 Correct 52 ms 16588 KB Output is correct
15 Correct 103 ms 53084 KB Output is correct
16 Correct 98 ms 47196 KB Output is correct
17 Correct 80 ms 46308 KB Output is correct
18 Correct 55 ms 19996 KB Output is correct
19 Correct 43 ms 18864 KB Output is correct
20 Correct 52 ms 19560 KB Output is correct
21 Correct 45 ms 18912 KB Output is correct
22 Correct 42 ms 18824 KB Output is correct
23 Correct 52 ms 19560 KB Output is correct
24 Correct 118 ms 66512 KB Output is correct
25 Correct 140 ms 69200 KB Output is correct
26 Correct 118 ms 64976 KB Output is correct
27 Correct 122 ms 66000 KB Output is correct
28 Correct 162 ms 33868 KB Output is correct
29 Correct 122 ms 27088 KB Output is correct