oj.uz

Submission #1047811

# Submission time Handle Problem Language Result Execution time Memory
1047811 2024-08-07T16:09:54 Z Tam_theguide Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 71 ms 89688 KB 
#include <bits/stdc++.h>
using namespace std;
const int LimitNM = 1e5;
const int LimitTrie = 2e6;
const int BUFFER = 1e9;
using Point = pair<int, int>;
int n, m, CharId[2310], QueryAns[LimitNM + 5];
Point RNATrieId[LimitNM + 5], QuerySuffixEuler[LimitNM + 5];
string s[LimitNM + 5];
vector<Point> Axis;
struct Trie {
    int cnt, nxt[LimitTrie][4], Eulercnt, In[LimitTrie], Out[LimitTrie];
    Trie() { cnt = Eulercnt = 0; }
    int TrieAdd(string& x, bool IsRNA) {
        int root = 0;
        for (int i = 0; i < x.size(); i++) {
            if (nxt[root][CharId[x[i]]] == 0)
                if (IsRNA) nxt[root][CharId[x[i]]] = ++cnt;
                else return 0;
            root = nxt[root][CharId[x[i]]];
        }
        return root;
    }
    void dfsEulerTour(int root) {
        In[root] = ++Eulercnt;
        for (int i = 0; i < 4; i++) {
            if (nxt[root][i] == 0)
                continue;
            dfsEulerTour(nxt[root][i]);
        }
        Out[root] = Eulercnt;
    }
} PrefixTrie, SuffixTrie;
int BIT[LimitTrie];
void BITAdd(int pos) {
    while (pos <= SuffixTrie.Eulercnt) {
        BIT[pos]++;
        pos += (pos & (-pos));
    }
}
int BITGetPre(int pos) {
    int Total = 0;
    while (pos > 0) {
        Total += BIT[pos];
        pos -= (pos & (-pos));
    }
    return Total;
}
int BITGetRange(int l, int r) {
    if (l > r) return 0;
    return BITGetPre(r) - BITGetPre(l - 1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    vector<char> CharList = {'A', 'G', 'C', 'U'};
    for (int i = 0; i < 4; i++) 
        CharId[CharList[i]] = i;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        RNATrieId[i].first = PrefixTrie.TrieAdd(s[i], true);
        reverse(s[i].begin(), s[i].end());
        RNATrieId[i].second = SuffixTrie.TrieAdd(s[i], true);
    }
    PrefixTrie.dfsEulerTour(0);
    SuffixTrie.dfsEulerTour(0);
    for (int i = 1; i <= n; i++) {
        RNATrieId[i].first = PrefixTrie.In[RNATrieId[i].first];
        RNATrieId[i].second = SuffixTrie.In[RNATrieId[i].second];
        Axis.push_back(RNATrieId[i]);
    }
    // s[i] = {prefixid, suffixid}, prefixtrie = {in, out}, suffixtrie = {in, out}
    for (int i = 1; i <= m; i++) {
        string p, q;
        cin >> p >> q;
        Point NonEulerId;
        NonEulerId.first = PrefixTrie.TrieAdd(p, false);
        reverse(q.begin(), q.end());
        NonEulerId.second = SuffixTrie.TrieAdd(q, false);
        if (min(NonEulerId.first, NonEulerId.second) == 0) continue;

        Axis.emplace_back(PrefixTrie.In[NonEulerId.first], -i);
        Axis.emplace_back(PrefixTrie.Out[NonEulerId.first], i + BUFFER);
        QuerySuffixEuler[i] = {SuffixTrie.In[NonEulerId.second], SuffixTrie.Out[NonEulerId.second]};
    }
    sort(Axis.begin(), Axis.end());

    // cout << "RNATRIEID\n";
    // for (int i = 1; i <= n; i++) {
    //     cout << RNATrieId[i].first << " " << RNATrieId[i].second << '\n';
    // }
    // cout << '\n';
    // for (auto& c : Axis) {
    //     if (c.second < 0) cout <<"Qin"<< c.first << ", " << -c.second << '\n';
    //     else if (c.second > BUFFER) cout <<"Qout"<< c.first << " " << c.second - BUFFER << '\n';
    //     else cout << c.first << " " << c.second << '\n';
    // }
    
    // for (int i = 1; i <= m; i++) {
    //     cout << QuerySuffixEuler[i].first << ", " << QuerySuffixEuler[i].second << '\n';
    // }
    // cout << "spec " << SuffixTrie.In[SuffixTrie.nxt[0][1]] << " " << SuffixTrie.Out[SuffixTrie.nxt[0][1]] << '\n';
    for (auto& c : Axis) {
        if (c.second < 0) {
            QueryAns[-c.second] -= BITGetRange(QuerySuffixEuler[-c.second].first, QuerySuffixEuler[-c.second].second);
        } else if (c.second > BUFFER) {
            QueryAns[c.second - BUFFER] += BITGetRange(QuerySuffixEuler[c.second - BUFFER].first, QuerySuffixEuler[c.second - BUFFER].second);
        } else {
            BITAdd(c.second);
        }
    }
    for (int i = 1; i <= m; i++)
        cout << QueryAns[i] << '\n';
}

Compilation message

selling_rna.cpp: In member function 'int Trie::TrieAdd(std::string&, bool)':
selling_rna.cpp:16:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |         for (int i = 0; i < x.size(); i++) {
      |                         ~~^~~~~~~~~~
selling_rna.cpp:17:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   17 |             if (nxt[root][CharId[x[i]]] == 0)
      |                                      ^
selling_rna.cpp:18:49: warning: array subscript has type 'char' [-Wchar-subscripts]
   18 |                 if (IsRNA) nxt[root][CharId[x[i]]] = ++cnt;
      |                                                 ^
selling_rna.cpp:17:16: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   17 |             if (nxt[root][CharId[x[i]]] == 0)
      |                ^
selling_rna.cpp:20:41: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |             root = nxt[root][CharId[x[i]]];
      |                                         ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:58:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   58 |         CharId[CharList[i]] = i;
      |                           ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 1 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 69460 KB Output is correct
2 Correct 51 ms 72272 KB Output is correct
3 Correct 63 ms 68176 KB Output is correct
4 Correct 49 ms 67484 KB Output is correct
5 Correct 66 ms 88964 KB Output is correct
6 Correct 66 ms 89688 KB Output is correct
7 Correct 32 ms 25940 KB Output is correct
8 Correct 48 ms 67224 KB Output is correct
9 Correct 49 ms 59144 KB Output is correct
10 Correct 40 ms 53880 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20952 KB Output is correct
2 Correct 13 ms 20064 KB Output is correct
3 Correct 16 ms 20008 KB Output is correct
4 Correct 13 ms 19932 KB Output is correct
5 Correct 13 ms 19924 KB Output is correct
6 Correct 18 ms 20056 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 18780 KB Output is correct
2 Correct 2 ms 18780 KB Output is correct
3 Correct 2 ms 18780 KB Output is correct
4 Correct 2 ms 18780 KB Output is correct
5 Correct 2 ms 18776 KB Output is correct
6 Correct 1 ms 18780 KB Output is correct
7 Correct 2 ms 18780 KB Output is correct
8 Correct 50 ms 69460 KB Output is correct
9 Correct 51 ms 72272 KB Output is correct
10 Correct 63 ms 68176 KB Output is correct
11 Correct 49 ms 67484 KB Output is correct
12 Correct 66 ms 88964 KB Output is correct
13 Correct 66 ms 89688 KB Output is correct
14 Correct 32 ms 25940 KB Output is correct
15 Correct 48 ms 67224 KB Output is correct
16 Correct 49 ms 59144 KB Output is correct
17 Correct 40 ms 53880 KB Output is correct
18 Correct 17 ms 20952 KB Output is correct
19 Correct 13 ms 20064 KB Output is correct
20 Correct 16 ms 20008 KB Output is correct
21 Correct 13 ms 19932 KB Output is correct
22 Correct 13 ms 19924 KB Output is correct
23 Correct 18 ms 20056 KB Output is correct
24 Correct 47 ms 68552 KB Output is correct
25 Correct 59 ms 69368 KB Output is correct
26 Correct 46 ms 67884 KB Output is correct
27 Correct 53 ms 63864 KB Output is correct
28 Correct 71 ms 39204 KB Output is correct
29 Correct 43 ms 26392 KB Output is correct