oj.uz

Submission #1081663

# Submission time Handle Problem Language Result Execution time Memory
1081663 2024-08-30T08:56:55 Z vjudge1 Selling RNA Strands (JOI16_selling_rna) C++17
100 / 100
 89 ms 70588 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());
    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';
}
/*
    Xay 2 cay Trie: mot cay cho tien to, mot cay cho hau to
    Khoi tao eulertour tren 2 cay trie
    --> Xau i thoa man truy van j khi va chi khi PrefixTrie.in[xau i] thuoc range cay con cua p[i] va SuffixTrie.in[xau i] thuoc range cay con cua q[i]
    --> neu coi {prefixtrie.in[xau i], suffixtrie.in[xau i]} la 1 diem va range cay con cua p[i] va q[i] tao thanh hinh chu nhat 
        (bo qua nhung truy van ma p[i] hoac q[i] khong co trong trie) 
        thi bai toan tro ve dem so diem thuoc hinh chu nhat
    **dem so diem thuoc hinh chu nhat** 
    them diem {prefixtrie.in[xau i], suffixtrie.in[xau i]} (diem loai 3) vao Axis
    them 2 dau cua range cay con cua p[i] vao Axis (dau nho hon loai 1, dau to hon loai 2)
    sap xep axis theo first, neu first = nhau thi sap xep theo uu tien loai 1 roi den loai 3, roi den loai 2
    den diem loai 1 thi ketqua truy van -= tong doan range cay con q[i] (lay bang BIT)
    den diem loai 2 thi ketqua truy van += tong doan range cay con q[i] (lay bang BIT)
    den diem loai 3 thi cong them 1 vao vi tri suffixtrie.in[xau i] trong BIT
*/

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 3672 KB Output is correct
2 Correct 2 ms 3636 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 1 ms 3672 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 62804 KB Output is correct
2 Correct 67 ms 60976 KB Output is correct
3 Correct 74 ms 55636 KB Output is correct
4 Correct 63 ms 53332 KB Output is correct
5 Correct 89 ms 69456 KB Output is correct
6 Correct 88 ms 70588 KB Output is correct
7 Correct 30 ms 10836 KB Output is correct
8 Correct 66 ms 48084 KB Output is correct
9 Correct 59 ms 42328 KB Output is correct
10 Correct 46 ms 38892 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6872 KB Output is correct
2 Correct 16 ms 5704 KB Output is correct
3 Correct 22 ms 6020 KB Output is correct
4 Correct 14 ms 5596 KB Output is correct
5 Correct 16 ms 5592 KB Output is correct
6 Correct 22 ms 6104 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3672 KB Output is correct
2 Correct 2 ms 3636 KB Output is correct
3 Correct 2 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 2 ms 3676 KB Output is correct
6 Correct 1 ms 3672 KB Output is correct
7 Correct 1 ms 3676 KB Output is correct
8 Correct 69 ms 62804 KB Output is correct
9 Correct 67 ms 60976 KB Output is correct
10 Correct 74 ms 55636 KB Output is correct
11 Correct 63 ms 53332 KB Output is correct
12 Correct 89 ms 69456 KB Output is correct
13 Correct 88 ms 70588 KB Output is correct
14 Correct 30 ms 10836 KB Output is correct
15 Correct 66 ms 48084 KB Output is correct
16 Correct 59 ms 42328 KB Output is correct
17 Correct 46 ms 38892 KB Output is correct
18 Correct 21 ms 6872 KB Output is correct
19 Correct 16 ms 5704 KB Output is correct
20 Correct 22 ms 6020 KB Output is correct
21 Correct 14 ms 5596 KB Output is correct
22 Correct 16 ms 5592 KB Output is correct
23 Correct 22 ms 6104 KB Output is correct
24 Correct 63 ms 54488 KB Output is correct
25 Correct 79 ms 55616 KB Output is correct
26 Correct 63 ms 53712 KB Output is correct
27 Correct 62 ms 47832 KB Output is correct
28 Correct 80 ms 21068 KB Output is correct
29 Correct 53 ms 12244 KB Output is correct