Submission #445832

#TimeUsernameProblemLanguageResultExecution timeMemory
445832JovanBSelling RNA Strands (JOI16_selling_rna)C++17
100 / 100
377 ms432864 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 100000; int x[N+5]; int y[N+5]; const int MAXC = 4000000; int gde[MAXC+5][4]; int tjm; vector <int> koji[MAXC+5]; vector <int> queries[MAXC+5]; void trie_add(int t, int ind, const string &s){ int v = 0; for(int i=0; i<s.size(); i++){ int x = s[i] - 'A'; if(!gde[v][x]){ gde[v][x] = ++tjm; } v = gde[v][x]; } if(t == 1) koji[v].push_back(ind); else queries[v].push_back(ind); } int xl[N+5], yl[N+5], xr[N+5], yr[N+5]; void dfs(int t, int v){ int in = ++tjm; for(auto c : koji[v]){ if(t == 1) x[c] = in; else y[c] = in; } for(int x=0; x<4; x++) if(gde[v][x]) dfs(t, gde[v][x]); int out = tjm; for(auto c : queries[v]){ if(t == 1){ xl[c] = in, xr[c] = out; } else{ yl[c] = in, yr[c] = out; } } queries[v].clear(); koji[v].clear(); for(int x=0; x<4; x++) gde[v][x] = 0; } string s[N+5]; string qpref[N+5]; string qsuf[N+5]; int bit[MAXC+5]; void bit_add(int x){ while(x <= MAXC){ bit[x]++; x += x & -x; } } int bit_get(int x){ int res = 0; while(x){ res += bit[x]; x -= x & -x; } return res; } const int INF = 1000000000; vector <int> upds[MAXC+5]; vector <pair <pair <int, int>, int>> quers[MAXC+5]; int res[N+5]; int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n, m; cin >> n >> m; for(int i=1; i<=n; i++){ cin >> s[i]; for(auto &c : s[i]){ if(c == 'G') c = 'B'; if(c == 'U') c = 'D'; } trie_add(1, i, s[i]); } for(int i=1; i<=m; i++){ cin >> qpref[i] >> qsuf[i]; for(auto &c : qpref[i]){ if(c == 'G') c = 'B'; if(c == 'U') c = 'D'; } for(auto &c : qsuf[i]){ if(c == 'G') c = 'B'; if(c == 'U') c = 'D'; } trie_add(2, i, qpref[i]); } dfs(1, 0); for(int i=1; i<=n; i++){ reverse(s[i].begin(), s[i].end()); trie_add(1, i, s[i]); } for(int i=1; i<=m; i++){ reverse(qsuf[i].begin(), qsuf[i].end()); trie_add(2, i, qsuf[i]); } tjm = 0; dfs(2, 0); for(int i=1; i<=n; i++){ upds[y[i]].push_back(x[i]); } for(int i=1; i<=m; i++){ quers[yr[i]].push_back({{xl[i], xr[i]}, i}); quers[yl[i] - 1].push_back({{xl[i], xr[i]}, -i}); } for(int i=1; i<=MAXC; i++){ for(auto c : upds[i]) bit_add(c); for(auto c : quers[i]){ int ind = c.second; int kf = 1; if(ind < 0){ ind = -ind; kf = -1; } res[ind] += kf*(bit_get(c.first.second) - bit_get(c.first.first - 1)); } } for(int i=1; i<=m; i++) cout << res[i] << "\n"; return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'void trie_add(int, int, const string&)':
selling_rna.cpp:22:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0; 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...