Submission #978652

#TimeUsernameProblemLanguageResultExecution timeMemory
978652thaibeo123Selling RNA Strands (JOI16_selling_rna)C++14
0 / 100
2 ms3420 KiB
#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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...