oj.uz

Submission #670717

# Submission time Handle Problem Language Result Execution time Memory
670717 2022-12-10T00:04:54 Z stevancv Selling RNA Strands (JOI16_selling_rna) C++14
100 / 100
 308 ms 321248 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 92 ms 188300 KB Output is correct
2 Correct 90 ms 188244 KB Output is correct
3 Correct 89 ms 188332 KB Output is correct
4 Correct 85 ms 188240 KB Output is correct
5 Correct 86 ms 188204 KB Output is correct
6 Correct 85 ms 188236 KB Output is correct
7 Correct 87 ms 188184 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 303064 KB Output is correct
2 Correct 244 ms 301644 KB Output is correct
3 Correct 266 ms 283692 KB Output is correct
4 Correct 256 ms 279220 KB Output is correct
5 Correct 303 ms 319300 KB Output is correct
6 Correct 308 ms 321248 KB Output is correct
7 Correct 127 ms 194204 KB Output is correct
8 Correct 237 ms 269632 KB Output is correct
9 Correct 209 ms 257384 KB Output is correct
10 Correct 189 ms 253004 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 189868 KB Output is correct
2 Correct 104 ms 189476 KB Output is correct
3 Correct 110 ms 189680 KB Output is correct
4 Correct 111 ms 189188 KB Output is correct
5 Correct 105 ms 189412 KB Output is correct
6 Correct 112 ms 189484 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 188300 KB Output is correct
2 Correct 90 ms 188244 KB Output is correct
3 Correct 89 ms 188332 KB Output is correct
4 Correct 85 ms 188240 KB Output is correct
5 Correct 86 ms 188204 KB Output is correct
6 Correct 85 ms 188236 KB Output is correct
7 Correct 87 ms 188184 KB Output is correct
8 Correct 260 ms 303064 KB Output is correct
9 Correct 244 ms 301644 KB Output is correct
10 Correct 266 ms 283692 KB Output is correct
11 Correct 256 ms 279220 KB Output is correct
12 Correct 303 ms 319300 KB Output is correct
13 Correct 308 ms 321248 KB Output is correct
14 Correct 127 ms 194204 KB Output is correct
15 Correct 237 ms 269632 KB Output is correct
16 Correct 209 ms 257384 KB Output is correct
17 Correct 189 ms 253004 KB Output is correct
18 Correct 115 ms 189868 KB Output is correct
19 Correct 104 ms 189476 KB Output is correct
20 Correct 110 ms 189680 KB Output is correct
21 Correct 111 ms 189188 KB Output is correct
22 Correct 105 ms 189412 KB Output is correct
23 Correct 112 ms 189484 KB Output is correct
24 Correct 242 ms 286984 KB Output is correct
25 Correct 255 ms 287712 KB Output is correct
26 Correct 248 ms 285556 KB Output is correct
27 Correct 246 ms 267260 KB Output is correct
28 Correct 199 ms 208068 KB Output is correct
29 Correct 142 ms 194312 KB Output is correct