Submission #213460

#TimeUsernameProblemLanguageResultExecution timeMemory
213460DS007Selling RNA Strands (JOI16_selling_rna)C++14
100 / 100
964 ms129892 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define int long long #define index_set tree<pair<string, int>, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> #define mid (l + r) / 2 #define child v * 2 const int N = 1e5; vector<string> t[N * 4]; string s[N]; bool compatible(const string &a, const string &b) { return a.substr(0, b.length()) == b; } string reverse(string a) { reverse(a.begin(), a.end()); return a; } void build(int v, int l, int r) { if (l == r) { t[v].push_back(reverse(s[l])); return; } build(child, l, mid); build(child + 1, mid + 1, r); int lp = 0, rp = 0; while (lp != t[child].size() && rp != t[child + 1].size()) { if (t[child][lp] < t[child + 1][rp]) t[v].push_back(t[child][lp++]); else t[v].push_back(t[child + 1][rp++]); } while (lp != t[child].size()) t[v].push_back(t[child][lp++]); while (rp != t[child + 1].size()) t[v].push_back(t[child + 1][rp++]); } int query(int v, int l, int r, int tl, int tr, pair<string, int> &up, pair<string, int> &down) { if (tl > tr) return 0; else if (l == tl && r == tr) return (lower_bound(t[v].begin(), t[v].end(), up.first) - t[v].begin()) - (lower_bound(t[v].begin(), t[v].end(), down.first) - t[v].begin()); return query(child, l, mid, tl, min(mid, tr), up, down) + query(child + 1, mid + 1, r, max(mid + 1, tl), tr, up, down); } void solveTestCase() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> s[i]; sort(s, s + n); build(1, 0, n - 1); /*for (int i = 0; i < n; i++) cout << s[i] << " "; cout << endl;*/ for (int i = 0; i < m; i++) { string p, q; cin >> p >> q; string temp = p; temp[p.length() - 1]++; int tl = lower_bound(s, s + n, p) - s, tr = lower_bound(s, s + n, temp) - s - 1; temp = reverse(q); temp[q.length() - 1]++; pair<string, int> up = {temp, -1}, down = {reverse(q), -1}; cout << query(1, 0, n - 1, tl, tr, up, down) << "\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test = 1; // cin >> test; while (test--) solveTestCase(); }

Compilation message (stderr)

selling_rna.cpp: In function 'void build(long long int, long long int, long long int)':
selling_rna.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size() && rp != t[child + 1].size()) {
            ~~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:34:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size() && rp != t[child + 1].size()) {
                                     ~~~^~~~~~~~~~~~~~~~~~~~~~
selling_rna.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (lp != t[child].size())
            ~~~^~~~~~~~~~~~~~~~~~
selling_rna.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (rp != t[child + 1].size())
            ~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...