Submission #978652

#	Time	Username	Problem	Language	Result	Execution time	Memory
978652		thaibeo123	Selling RNA Strands (JOI16_selling_rna)	C++14	0 / 100	2 ms	3420 KiB

selling_rna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
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.pb(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.fi) - p->h.begin() - 1;
        int large = upper_bound(p->h.begin(), p->h.end(), range.se) - p->h.begin() - 1;
        return large - small;
    }
};
int n, m;
string s[N], p, q;
Trie trie1;
RevTrie trie2;
int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    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:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         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:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In member function 'void RevTrie::add(std::string&, int)':
selling_rna.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         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:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i < s.size(); ++i){
      |                         ~~^~~~~~~~~~
selling_rna.cpp: In function 'char getchar(int)':
selling_rna.cpp:20:1: warning: control reaches end of non-void function [-Wreturn-type]
   20 | }
      | ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:92:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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