Submission #375886

#TimeUsernameProblemLanguageResultExecution timeMemory
375886mihai145Selling RNA Strands (JOI16_selling_rna)C++14
100 / 100
352 ms199240 KiB
#include <iostream> #include <string> #include <vector> using namespace std; const int NMAX = 1e5; const int QMAX = 1e5; struct Node { Node* sons[4]; vector <int> wordList; pair <int, int> wordRange; Node() { for(int i = 0; i < 4; i++) { sons[i] = NULL; } } }; int N, Q; string s; Node *pref = new Node, *suf = new Node; int GetSon(char s) { if(s == 'A') { return 0; } else if(s == 'G') { return 1; } else if(s == 'C') { return 2; } return 3; } void InsertPref(Node* node, int index, int id) { if(index == (int)s.size()) { node-> wordList.push_back(id); return; } int son = GetSon(s[index]); if(node-> sons[son] == NULL) { node-> sons[son] = new Node; } InsertPref(node-> sons[son], index + 1, id); } void InsertSuf(Node* node, int index, int id) { if(index == -1) { node-> wordList.push_back(id); return; } int son = GetSon(s[index]); if(node-> sons[son] == NULL) { node-> sons[son] = new Node; } InsertSuf(node-> sons[son], index - 1, id); } string pr, sf; vector<int> wordsWithPref, wordsWithSuf; vector <int> prefOrder; vector <int> sufOrder; void DfsPref(Node* root) { if(root == NULL) { return ; } root->wordRange.first = (int)prefOrder.size() + 1; for(int word : root-> wordList) { prefOrder.push_back(word); } for(int j = 0; j < 4; j++) { DfsPref(root-> sons[j]); } root->wordRange.second = (int)prefOrder.size(); } void DfsSuf(Node* root) { if(root == NULL) { return ; } root->wordRange.first = (int)sufOrder.size() + 1; for(int word : root-> wordList) { sufOrder.push_back(word); } for(int j = 0; j < 4; j++) { DfsSuf(root-> sons[j]); } root->wordRange.second = (int)sufOrder.size(); } pair<int, int> GetRangePref(Node* root, int index) { if(root == NULL) { return {-1, -1}; } if(index == (int)pr.size()) { return root-> wordRange; } int son = GetSon(pr[index]); return GetRangePref(root-> sons[son], index + 1); } pair<int, int> GetRangeSuf(Node* root, int index) { if(root == NULL) { return {-1, -1}; } if(index == -1) { return root-> wordRange; } int son = GetSon(sf[index]); return GetRangeSuf(root-> sons[son], index - 1); } int posSuf[NMAX + 2], matchLine[NMAX + 2]; struct LineQuery { int l, r, ind; }; vector<LineQuery> lineQueries[NMAX + 2]; int k, ansLine[2 * QMAX + 2]; pair <int, int> qrl[QMAX + 2]; int ans[QMAX + 2]; int aib[NMAX + 2]; inline int LSB(int x) { return x & (-x); } void Update(int pos) { for(int i = pos; i <= N; i += LSB(i)) { aib[i]++; } } int Query(int pos) { int ans = 0; for(int i = pos; i > 0; i -= LSB(i)) { ans += aib[i]; } return ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> Q; for(int i = 1; i <= N; i++) { cin >> s; InsertPref(pref, 0, i); InsertSuf(suf, (int)s.size() - 1, i); } DfsPref(pref); DfsSuf(suf); for(int i = 1; i <= Q; i++) { cin >> pr >> sf; pair <int, int> rangePref = GetRangePref(pref, 0); pair <int, int> rangeSuf = GetRangeSuf(suf, (int)sf.size() - 1); if(rangePref.first == -1 || rangeSuf.first == -1 || (rangePref.first > rangePref.second) || (rangeSuf.first > rangeSuf.second)) { ans[i] = 0; } else { ++k; lineQueries[rangePref.second].push_back({rangeSuf.first, rangeSuf.second, k}); ++k; lineQueries[rangePref.first - 1].push_back({rangeSuf.first, rangeSuf.second, k}); qrl[i] = {k - 1, k}; } } for(int i = 0; i < N; i++) { posSuf[sufOrder[i]] = i + 1; } for(int i = 0; i < N; i++) { matchLine[i + 1] = posSuf[prefOrder[i]]; } for(int i = 1; i <= N; i++) { Update(matchLine[i]); for(LineQuery lq : lineQueries[i]) { ansLine[lq.ind] = Query(lq.r) - Query(lq.l - 1); } } for(int i = 1; i <= Q; i++) { if(qrl[i].first != 0) { ans[i] = ansLine[qrl[i].first] - ansLine[qrl[i].second]; } } for(int i = 1; i <= Q; i++) { cout << ans[i] << '\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...