Submission #1087852

#TimeUsernameProblemLanguageResultExecution timeMemory
1087852LOLOLOSelling RNA Strands (JOI16_selling_rna)C++17
35 / 100
53 ms67152 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e5 + 100; map <int, int> id[N]; vector <int> pos[N]; int cnt = 1; void add(string s, int i) { int cur = 0; for (auto x : s) { if (id[cur][x] == 0) id[cur][x] = cnt++; cur = id[cur][x]; pos[cur].pb(i); } } int get(string s, int l, int r) { int cur = 0; for (auto x : s) { if (id[cur][x] == 0) return 0; cur = id[cur][x]; } int L = lower_bound(all(pos[cur]), l) - pos[cur].begin(); int R = upper_bound(all(pos[cur]), r) - pos[cur].begin(); return R - L; } void solve() { int n, m; cin >> n >> m; vector <string> ss; for (int i = 0; i < n; i++) { string s; cin >> s; ss.pb(s); } sort(all(ss)); for (int i = 0; i < sz(ss); i++) { string s = ss[i]; reverse(all(s)); add(s, i); } for (int i = 0; i < m; i++) { string a, b; cin >> a >> b; int l = lower_bound(all(ss), a) - ss.begin(); a.back()++; int r = lower_bound(all(ss), a) - ss.begin() - 1; if (l > r) { cout << 0 << '\n'; continue; } reverse(all(b)); cout << get(b, l, r) << '\n'; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; while (t--) { solve(); //cout << solve() << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...