Submission #978655

#	Time	Username	Problem	Language	Result	Execution time	Memory
978655		thaibeo123	Selling RNA Strands (JOI16_selling_rna)	C++14	100 / 100	219 ms	190360 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int getval(char s){
    if (s == 'A') return 0;
    else if (s == 'G') return 1;
    else if (s == 'C') return 2;
    else return 3;
}
char getchar(int c){
    if (c == 0) return 'A';
    else if (c == 1) return 'G';
    else if (c == 2) return 'C';
    else if (c == 3) return 'U';
}
struct Trie{
    struct Node{
        int l, r;
        Node *a[4];
        Node(){
            l = (int)1e9;
            r = (int)-1e9;
            for (int i = 0; i <= 3; ++i)
                a[i] = NULL;
        }
    };
    Node *root = new Node();
    void add(string &s, int id){
        Node *p = root;
        for (int i = 0; i < s.size(); ++i){
            int c = getval(s[i]);
            if (p->a[c] == NULL) p->a[c] = new Node();
            p = p->a[c];
            p->l = min(p->l, id);
            p->r = max(p->r, id);
        }
    }
    pair<int, int> getrange(string &s){
        Node *p = root;
        for (int i = 0; i < s.size(); ++i){
            int c = getval(s[i]);
            if (p->a[c] == NULL) return {0, 0};
            p = p->a[c];
        }
        return {p->l, p->r};
    }
};
struct RevTrie{
    struct Node{
        Node *a[4];
        vector<int> h;
        Node(){
            for (int i = 0; i <= 3; ++i)
                a[i] = NULL;
        }
    };
    Node *root = new Node();
    void add(string &s, int id){
        reverse(s.begin(), s.end());
        Node *p = root;
        for (int i = 0; i < s.size(); ++i){
            int c = getval(s[i]);
            if (p->a[c] == NULL) p->a[c] = new Node();
            p = p->a[c];
            p->h.push_back(id);
        }
    }
    int match(string &s, pair<int, int> range){
        reverse(s.begin(), s.end());
        Node *p = root;
        for (int i = 0; i < s.size(); ++i){
            int c = getval(s[i]);
            if (p->a[c] == NULL) return 0;
            p = p->a[c];
        }
        int small = lower_bound(p->h.begin(), p->h.end(), range.first) - p->h.begin() - 1;
        int large = upper_bound(p->h.begin(), p->h.end(), range.second) - p->h.begin() - 1;
        return large - small;
    }
};
int n, m;
string s[N], p, q;
Trie trie1;
RevTrie trie2;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> s[i];
    }
    sort(s + 1, s + 1 + n);
    for (int i = 1; i <= n; ++i){
        trie1.add(s[i], i);
        trie2.add(s[i], i);
    }
    while(m--){
        cin >> p >> q;
        cout << trie2.match(q, trie1.getrange(p)) << "\n";
    }
    return 0;
}

Compilation message (stderr)

selling_rna.cpp: In member function 'void Trie::add(std::string&, int)':
selling_rna.cpp:30:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'std::pair<int, int> Trie::getrange(std::string&)':
selling_rna.cpp:40:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void RevTrie::add(std::string&, int)':
selling_rna.cpp:61:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'int RevTrie::match(std::string&, std::pair<int, int>)':
selling_rna.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In function 'char getchar(int)':
selling_rna.cpp:15:1: warning: control reaches end of non-void function [-Wreturn-type]
   15 | }
      | ^

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