Submission #973084

#TimeUsernameProblemLanguageResultExecution timeMemory
973084duckindogSelling RNA Strands (JOI16_selling_rna)C++17
0 / 100
63 ms86100 KiB
#include <bits/stdc++.h> using namespace std; const int N = 100'000 + 10; int n, m; string str[N]; string s[N], e[N]; int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; } struct Trie { bool pass; int nwt[N << 3][4], ma[N << 3], mi[N << 3], sz[N << 3], it; Trie() { memset(mi, 63, sizeof mi); } void clear() { memset(nwt, 0, sizeof nwt); memset(ma, 0, sizeof ma); it = 0; pass = true; } void add(const auto& s, const int& node) { int g = 0; for (int i = 1; i <= s.size(); ++i) { int path = convert(s[i - 1]); if (!nwt[g][path]) nwt[g][path] = ++it; g = nwt[g][path]; ma[g] = max(ma[g], node); mi[g] = min(mi[g], node); sz[g] += pass; } } pair<int, int> que(const auto& s) { int g = 0; for (int i = 1; i <= s.size(); ++i) { int path = convert(s[i - 1]); if (!nwt[g][path]) return {0, 0}; g = nwt[g][path]; } return {pass ? sz[g] : mi[g], ma[g]}; } } T; vector<int> l[N], r[N]; int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= n; ++i) cin >> str[i]; for (int i = 1; i <= m; ++i) cin >> s[i] >> e[i]; for (int i = 1; i <= n; ++i) T.add(str[i], i); for (int i = 1; i <= m; ++i) { reverse(e[i].begin(), e[i].end()); const auto& [st, ed] = (T.que(s[i])); if (st) l[st - 1].push_back(i); r[ed].push_back(i); } T.clear(); vector<int> answer(m + 1); for (int i = 1; i <= n; ++i) { T.add(string(str[i].rbegin(), str[i].rend()), i); for (const auto& j : l[i]) answer[j] -= T.que(e[j]).first; for (const auto& j : r[i]) answer[j] += T.que(e[j]).first; } for (int i = 1; i <= m; ++i) cout << answer[i] << "\n"; }

Compilation message (stderr)

selling_rna.cpp:10:19: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   10 | int convert(const auto& a) { return a == 'A' ? 0 : a == 'C' ? 1 : a == 'G' ? 2 : 3; }
      |                   ^~~~
selling_rna.cpp:27:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   27 |   void add(const auto& s, const int& node) {
      |                  ^~~~
selling_rna.cpp:40:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   40 |   pair<int, int> que(const auto& s) {
      |                            ^~~~
selling_rna.cpp: In instantiation of 'void Trie::add(const auto:24&, const int&) [with auto:24 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:62:47:   required from here
selling_rna.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 1; i <= s.size(); ++i) {
      |                     ~~^~~~~~~~~~~
selling_rna.cpp: In instantiation of 'std::pair<int, int> Trie::que(const auto:25&) [with auto:25 = std::__cxx11::basic_string<char>]':
selling_rna.cpp:65:39:   required from here
selling_rna.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 1; i <= s.size(); ++i) {
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...