selling_rna.cpp:1:138: warning: extra tokens at end of #include directive
1 | /* Author: Cadocx Codeforces: https://codeforces.com/profile/Kadoc VNOJ: oj.vnoi.info/user/Cadoc*/#include <bits/stdc++.h>using namespace std;// input/output#define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define el cout << '\n'#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"// #pragma GCC optimize("O2")// #pragma GCC optimize("Ofast")// #pragma GCC target("avx,avx2,fma")//data type#define ll long long#define ull unsigned long long#define pii pair<int, int>#define pll pair<ll, ll>#define piv pair<int, vector<int>>#define vi vector<int>#define vl vector<ll>#define vc vector<char>//STL#define sz(x) (int)(x).size()#define for1(i,l,r) for(auto i = l; i <= r; i++)#define for2(i,r,l) for(auto i = r; i >= l; i--)#define forin(i,a) for(auto i : a)#define pb push_back#define eb emplace_back#define pf push_front#define all(x) (x).begin(), (x).end()#define fi first#define se second//bitmask#define bitcnt(n) __builtin_popcount(n)#define mask(i) (1 << (i))#define bit(n, i) (((n) >> (i)) & 1)#define set_on(n, i) ((n) | mask(i))#define set_off(n, i) ((n) & ~mask(i))//constant#define N 100005#define MOD 1000000009#define INF 0x3f3f3f3f#define LINF 0x3f3f3f3f3f3f3f3f#define base 31#define Kadoc 0int n, m;string str[N];struct Query{ string p, q;} qr[N];void remap(string &s){ int n = s.size(); for(int i=0; i<n; ++i){ if(s[i] == 'A') s[i] = 'a'; else if(s[i] == 'G') s[i] = 'b'; else if(s[i] == 'U') s[i] = 'c'; else if(s[i] == 'C') s[i] = 'd'; }}void Init(){ cin >> n >> m; for(int i=1; i<=n; ++i) cin >> str[i]; for(int i=1; i<=m; ++i) cin >> qr[i].p >> qr[i].q;}bool checkSubtask1(){ int ss = 0, sp = 0, sq = 0; for(int i=1; i<=n; ++i) ss += str[i].size(); for(int i=1; i<=m; ++i) sp += qr[i].p.size(), sq += qr[i].q.size(); return n <= 100 && m <= 100 && ss <= 100 && sp <= 100 && sq <= 100;}namespace subtask1{ bool check(string a, string b, string c){ int n = a.size(), m = b.size(), p = c.size(); if(n > p || m > p) return 0; for(int i=0; i<n; ++i) if(c[i] != a[i]) return 0; for(int i=p-m; i<p; ++i) if(c[i] != b[i-p+m]) return 0; return 1; } void solve(){ for(int i=1; i<=m; ++i){ string p = qr[i].p, q = qr[i].q; int ans = 0; for(int j=1; j<=n; ++j) ans += check(p, q, str[j]); cout << ans; el; } }}bool checkSubtask2(){ return n <= 5000 && m <= 5000;}namespace subtask2{ const int mxN = 1e5; ll p[N]; vector<ll> hs[N]; ll get(int id, int l, int r){ return ((hs[id][r] - hs[id][l-1] * p[r-l+1]) % MOD + MOD) % MOD; } void solve(){ p[0] = 1; for(int i=1; i<=mxN; ++i) p[i] = p[i-1] * base % MOD; for(int i=1; i<=n; ++i){ ll cur = 0; string s = str[i]; int p = s.size(); hs[i].pb(0); for(int j=0; j<p; ++j){ cur = (cur * base + s[j] - 'A' + 1) % MOD; hs[i].pb(cur); } } for(int i=1; i<=m; ++i){ string s = qr[i].p, t = qr[i].q; int p = s.size(), q = t.size(); ll hp = 0, hq = 0; for(int j=0; j<p; ++j) hp = (hp * base + s[j] - 'A' + 1) % MOD; for(int j=0; j<q; ++j) hq = (hq * base + t[j] - 'A' + 1) % MOD; int ans = 0; for(int j=1; j<=n; ++j){ int k = str[j].size(); if(p > k || q > k) continue; ll a = get(j, 1, p), b = get(j, k-q+1, k); ans += (a == hp && b == hq); } cout << ans; el; } }}namespace subtask4{ struct Node{ Node* child[4]; int l, r; vector<int> v; Node(){ memset(child, NULL, sizeof child); l = r = 0; } }; Node* root = new Node(); void addpref(int id, string s){ Node* u = root; int n = s.size(); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) u -> child[k] = new Node(); u = u -> child[k]; if(!u -> l) u -> l = id; u -> r = id; } } void addsuf(int id, string s){ Node* u = root; int n = s.size(); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) u -> child[k] = new Node(); u = u -> child[k]; (u -> v).pb(id); } } pii getpref(string s){ Node* u = root; int n = s.size(); pii dead = pii(-1, -1); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) return dead; u = u -> child[k]; } return pii(u -> l, u -> r); } vi getsuf(string s){ Node* u = root; int n = s.size(); vi dead = {-1}; for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) return dead; u = u -> child[k]; } return u -> v; } void solve(){ for(int i=1; i<=n; ++i) remap(str[i]); for(int i=1; i<=m; ++i) remap(qr[i].p), remap(qr[i].q); sort(str+1, str+n+1); for(int i=1; i<=n; ++i){ addpref(i, str[i]); string s = str[i]; reverse(all(s)); addsuf(i, s); } for(int i=1; i<=m; ++i){ string s = qr[i].p, t = qr[i].q; reverse(all(t)); pii tmp = getpref(s); vi v = getsuf(t); int l = tmp.fi, r = tmp.se; // for(int x:v) cout << x << ' '; el; int ansl = lower_bound(all(v), l) - v.begin(), ansr = upper_bound(all(v), r) - v.begin(); cout << ansr - ansl; el; } }}void Solve(){ // if(checkSubtask1()) return subtask1::solve(); // if(checkSubtask2()) return subtask2::solve(); subtask4::solve();}int main(){ #define NAME "TASK" if(fopen(NAME".inp", "r")){ freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout); } fastIO; Init(); Solve(); return execute, 0;}
| ^~~~~~~~~
selling_rna.cpp:1:117: fatal error: bits/stdc++.h>usin: No such file or directory
1 | /* Author: Cadocx Codeforces: https://codeforces.com/profile/Kadoc VNOJ: oj.vnoi.info/user/Cadoc*/#include <bits/stdc++.h>using namespace std;// input/output#define fastIO ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)#define el cout << '\n'#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"// #pragma GCC optimize("O2")// #pragma GCC optimize("Ofast")// #pragma GCC target("avx,avx2,fma")//data type#define ll long long#define ull unsigned long long#define pii pair<int, int>#define pll pair<ll, ll>#define piv pair<int, vector<int>>#define vi vector<int>#define vl vector<ll>#define vc vector<char>//STL#define sz(x) (int)(x).size()#define for1(i,l,r) for(auto i = l; i <= r; i++)#define for2(i,r,l) for(auto i = r; i >= l; i--)#define forin(i,a) for(auto i : a)#define pb push_back#define eb emplace_back#define pf push_front#define all(x) (x).begin(), (x).end()#define fi first#define se second//bitmask#define bitcnt(n) __builtin_popcount(n)#define mask(i) (1 << (i))#define bit(n, i) (((n) >> (i)) & 1)#define set_on(n, i) ((n) | mask(i))#define set_off(n, i) ((n) & ~mask(i))//constant#define N 100005#define MOD 1000000009#define INF 0x3f3f3f3f#define LINF 0x3f3f3f3f3f3f3f3f#define base 31#define Kadoc 0int n, m;string str[N];struct Query{ string p, q;} qr[N];void remap(string &s){ int n = s.size(); for(int i=0; i<n; ++i){ if(s[i] == 'A') s[i] = 'a'; else if(s[i] == 'G') s[i] = 'b'; else if(s[i] == 'U') s[i] = 'c'; else if(s[i] == 'C') s[i] = 'd'; }}void Init(){ cin >> n >> m; for(int i=1; i<=n; ++i) cin >> str[i]; for(int i=1; i<=m; ++i) cin >> qr[i].p >> qr[i].q;}bool checkSubtask1(){ int ss = 0, sp = 0, sq = 0; for(int i=1; i<=n; ++i) ss += str[i].size(); for(int i=1; i<=m; ++i) sp += qr[i].p.size(), sq += qr[i].q.size(); return n <= 100 && m <= 100 && ss <= 100 && sp <= 100 && sq <= 100;}namespace subtask1{ bool check(string a, string b, string c){ int n = a.size(), m = b.size(), p = c.size(); if(n > p || m > p) return 0; for(int i=0; i<n; ++i) if(c[i] != a[i]) return 0; for(int i=p-m; i<p; ++i) if(c[i] != b[i-p+m]) return 0; return 1; } void solve(){ for(int i=1; i<=m; ++i){ string p = qr[i].p, q = qr[i].q; int ans = 0; for(int j=1; j<=n; ++j) ans += check(p, q, str[j]); cout << ans; el; } }}bool checkSubtask2(){ return n <= 5000 && m <= 5000;}namespace subtask2{ const int mxN = 1e5; ll p[N]; vector<ll> hs[N]; ll get(int id, int l, int r){ return ((hs[id][r] - hs[id][l-1] * p[r-l+1]) % MOD + MOD) % MOD; } void solve(){ p[0] = 1; for(int i=1; i<=mxN; ++i) p[i] = p[i-1] * base % MOD; for(int i=1; i<=n; ++i){ ll cur = 0; string s = str[i]; int p = s.size(); hs[i].pb(0); for(int j=0; j<p; ++j){ cur = (cur * base + s[j] - 'A' + 1) % MOD; hs[i].pb(cur); } } for(int i=1; i<=m; ++i){ string s = qr[i].p, t = qr[i].q; int p = s.size(), q = t.size(); ll hp = 0, hq = 0; for(int j=0; j<p; ++j) hp = (hp * base + s[j] - 'A' + 1) % MOD; for(int j=0; j<q; ++j) hq = (hq * base + t[j] - 'A' + 1) % MOD; int ans = 0; for(int j=1; j<=n; ++j){ int k = str[j].size(); if(p > k || q > k) continue; ll a = get(j, 1, p), b = get(j, k-q+1, k); ans += (a == hp && b == hq); } cout << ans; el; } }}namespace subtask4{ struct Node{ Node* child[4]; int l, r; vector<int> v; Node(){ memset(child, NULL, sizeof child); l = r = 0; } }; Node* root = new Node(); void addpref(int id, string s){ Node* u = root; int n = s.size(); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) u -> child[k] = new Node(); u = u -> child[k]; if(!u -> l) u -> l = id; u -> r = id; } } void addsuf(int id, string s){ Node* u = root; int n = s.size(); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) u -> child[k] = new Node(); u = u -> child[k]; (u -> v).pb(id); } } pii getpref(string s){ Node* u = root; int n = s.size(); pii dead = pii(-1, -1); for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) return dead; u = u -> child[k]; } return pii(u -> l, u -> r); } vi getsuf(string s){ Node* u = root; int n = s.size(); vi dead = {-1}; for(int i=0; i<n; ++i){ int k = s[i] - 'a'; if(!u -> child[k]) return dead; u = u -> child[k]; } return u -> v; } void solve(){ for(int i=1; i<=n; ++i) remap(str[i]); for(int i=1; i<=m; ++i) remap(qr[i].p), remap(qr[i].q); sort(str+1, str+n+1); for(int i=1; i<=n; ++i){ addpref(i, str[i]); string s = str[i]; reverse(all(s)); addsuf(i, s); } for(int i=1; i<=m; ++i){ string s = qr[i].p, t = qr[i].q; reverse(all(t)); pii tmp = getpref(s); vi v = getsuf(t); int l = tmp.fi, r = tmp.se; // for(int x:v) cout << x << ' '; el; int ansl = lower_bound(all(v), l) - v.begin(), ansr = upper_bound(all(v), r) - v.begin(); cout << ansr - ansl; el; } }}void Solve(){ // if(checkSubtask1()) return subtask1::solve(); // if(checkSubtask2()) return subtask2::solve(); subtask4::solve();}int main(){ #define NAME "TASK" if(fopen(NAME".inp", "r")){ freopen(NAME".inp", "r", stdin); freopen(NAME".out", "w", stdout); } fastIO; Init(); Solve(); return execute, 0;}
| ^~~~~~~~~~~~~~~~~~~~
compilation terminated.