Submission #670717

#	Time	Username	Problem	Language	Result	Execution time	Memory
670717		stevancv	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	308 ms	321248 KiB

selling_rna

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e6 + 2;
const int M = 2e6 + 2;
const int inf = 2e9;
int Convert(char x) {
    if (x == 'A') return 0;
    if (x == 'C') return 1;
    if (x == 'G') return 2;
    if (x == 'U') return 3;
}
vector<int> a[M];
int b[N];
struct Trie {
    vector<int> g[M];
    int nxt[M][4], tsz, in[M], out[M];
    int Add(string s) {
        int node = 0;
        for (int i = 0; i < s.size(); i++) {
            int y = Convert(s[i]);
            if (nxt[node][y] == 0) nxt[node][y] = ++tsz, g[node].push_back(tsz);
            node = nxt[node][y];
        }
        return node;
    }
    int Get(string s) {
        int node = 0;
        for (int i = 0; i < s.size(); i++) {
            int y = Convert(s[i]);
            if (nxt[node][y] == 0) return -1;
            node = nxt[node][y];
        }
        return node;
    }
    int Compute(int s, int x) {
        in[s] = x;
        for (int u : g[s]) {
            x = Compute(u, x + 1);
        }
        return out[s] = x;
    }

}pre, suf;
vector<pair<int, int>> qq[N];
struct Bit {
    int bit[N];
    void Add(int x) {
        x += 1;
        for (; x < N; x += x & (-x)) bit[x]++;
    }
    int F(int x) {
        x += 1; int ans = 0;
        for (; x > 0; x -= x & (-x)) ans += bit[x];
        return ans;
    }
    int Get(int l, int r) {
        return F(r) - F(l - 1);
    }
}f;
int ans[N];
void Dfs(int s) {
    for (auto u : qq[s]) {
        ans[u.second] -= f.Get(suf.in[u.first], suf.out[u.first]);
    }
    for (int u : a[s]) f.Add(suf.in[b[u]]);
    for (int i = 0; i < 4; i++) {
        if (pre.nxt[s][i]) Dfs(pre.nxt[s][i]);
    }
    for (auto u : qq[s]) {
        ans[u.second] += f.Get(suf.in[u.first], suf.out[u.first]);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        int x = pre.Add(s);
        reverse(s.begin(), s.end());
        int y = suf.Add(s);
        a[x].push_back(i);
        b[i] = y;
    }
    suf.Compute(0, 0);
    for (int i = 0; i < m; i++) {
        string s, t;
        cin >> s >> t;
        int x = pre.Get(s);
        reverse(t.begin(), t.end());
        int y = suf.Get(t);
        if (min(x, y) > -1) qq[x].push_back({y, i});
    }
    Dfs(0);
    for (int i = 0; i < m; i++) cout << ans[i] << en;
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'int Trie::Add(std::string)':
selling_rna.cpp:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int Trie::Get(std::string)':
selling_rna.cpp:34:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i = 0; i < s.size(); i++) {
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In function 'int Convert(char)':
selling_rna.cpp:17:1: warning: control reaches end of non-void function [-Wreturn-type]
   17 | }
      | ^

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