Submission #78404

#TimeUsernameProblemLanguageResultExecution timeMemory
78404MladenPSelling RNA Strands (JOI16_selling_rna)C++17
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> #define STIZE(x) fprintf(stderr, "STIZE%d\n", x); #define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x); #define NL(x) printf("%c", " \n"[(x)]); #define lld long long #define pii pair<int,int> #define pb push_back #define fi first #define se second #define mid (l+r)/2 #define endl '\n' #define all(a) begin(a),end(a) #define sz(a) int((a).size()) #define LINF 1000000000000000LL #define INF 1000000000 #define EPS 1e-9 using namespace std; #define MAXL 1000000 #define MAXN 100010 #define MOD 1000000007 int trie[MAXL][4], siz[MAXL], idx[MAXL], nodes, timer, hshidx, key, f[300]; bool sorted[MAXL]; vector<int> gde[MAXL], celi; map<int,int> cudo; lld hsh[MAXN], hsh1[MAXN], st[MAXN]; char P[MAXN], Q[MAXN], S[MAXN]; void ubaci(int node, char s[], int idx, int len) { if(idx == len) return; int c = f[s[idx]]; if(trie[node][c] == 0) trie[node][c] = ++nodes; gde[hsh[len-1-idx]].pb(node); ubaci(trie[node][c], s, idx+1, len); } int DFS(int node) { idx[node] = ++timer; for(int i = 0; i < 4; i++) if(trie[node][i]) siz[node] += DFS(trie[node][i]); return ++siz[node]; } void hashuj(char s[], lld hsh[], int lens) { fill(hsh, hsh+lens+5, 0); for(int i = 0; i < lens; i++) { hsh[i] += st[i]*(f[s[i]]+1); if(hsh[i] >= MOD) hsh[i] %= MOD; hsh[i+1] += hsh[i]; if(cudo[hsh[i]] == 0) cudo[hsh[i]] = ++hshidx; hsh[i] = cudo[hsh[i]]; } } void hashuj1(char s[], lld hsh[], int lens) { fill(hsh, hsh+lens+5, 0); for(int i = 0; i < lens; i++) { hsh[i] += st[i]*(f[s[i]]+1); if(hsh[i] >= MOD) hsh[i] %= MOD; hsh[i+1] += hsh[i]; } } int query(int node, char s[], int idxx, int len) { if(idxx == len) return node; int c = f[s[idxx]]; if(trie[node][c] == 0) return -1; return query(trie[node][c], s, idxx+1, len); } int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); int N, M; scanf("%d%d", &N, &M); f['A'] = 0, f['G'] = 1, f['C'] = 2, f['U'] = 3, st[0] = 1; for(int i = 1; i < MAXN; i++) st[i] = (st[i-1]*5 >= MOD ? (st[i-1]*5)%MOD : st[i-1]*5); for(int i = 1; i <= N; i++) { scanf("%s", S); int lenS = strlen(S); reverse(S, S+lenS); hashuj1(S, hsh, lens); celi.pb(hsh[lenS-1]); hashuj(S, hsh, lenS); reverse(S, S+lenS); ubaci(0, S, 0, lenS); } int kol = hshidx; sort(all(celi)); DFS(0); for(int q = 0; q < M; q++) { int rez = 0; scanf("%s%s", P, Q); int lenQ = strlen(Q), lenP = strlen(P); reverse(Q, Q+lenQ); hashuj1(Q, hsh, lenQ); key = cudo[hsh[lenQ-1]]; int koji = query(0, P, 0, lenP); if(key == 0 || koji == -1) { printf("0\n"); return 0; } if(!sorted[key]) { for(int i = 0; i < sz(gde[key]); i++) gde[key][i] = idx[gde[key][i]]; sort(all(gde[key])); sorted[key] = 1; } reverse(P, P+lenP); hashuj1(P, hsh1, lenP); hashuj1(Q, hsh, lenQ); for(int i = 0; i < lenQ; i++) { if(hsh[lenQ-1] - hsh[lenQ-2-i] == hsh1[i]*st[lenQ-i-1]) { lld cur = hsh1[lenP-1]*st[lenQ-i-1] + hsh[lenQ-2-i]; rez += upper_bound(all(celi), cur) - lower_bound(all(celi), cur); } } rez += upper_bound(all(gde[key]), idx[koji]+siz[koji]-1) - lower_bound(all(gde[key]), idx[koji]); printf("%d\n", rez); } return 0; }

Compilation message (stderr)

selling_rna.cpp: In function 'void ubaci(int, char*, int, int)':
selling_rna.cpp:29:21: warning: array subscript has type 'char' [-Wchar-subscripts]
     int c = f[s[idx]];
                     ^
selling_rna.cpp: In function 'void hashuj(char*, long long int*, int)':
selling_rna.cpp:42:32: warning: array subscript has type 'char' [-Wchar-subscripts]
         hsh[i] += st[i]*(f[s[i]]+1);
                                ^
selling_rna.cpp: In function 'void hashuj1(char*, long long int*, int)':
selling_rna.cpp:52:32: warning: array subscript has type 'char' [-Wchar-subscripts]
         hsh[i] += st[i]*(f[s[i]]+1);
                                ^
selling_rna.cpp: In function 'int query(int, char*, int, int)':
selling_rna.cpp:59:22: warning: array subscript has type 'char' [-Wchar-subscripts]
     int c = f[s[idxx]];
                      ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:73:25: error: 'lens' was not declared in this scope
         hashuj1(S, hsh, lens);
                         ^~~~
selling_rna.cpp:73:25: note: suggested alternative: 'lenS'
         hashuj1(S, hsh, lens);
                         ^~~~
                         lenS
selling_rna.cpp:79:9: warning: unused variable 'kol' [-Wunused-variable]
     int kol = hshidx;
         ^~~
selling_rna.cpp:66:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int N, M; scanf("%d%d", &N, &M);
               ~~~~~^~~~~~~~~~~~~~~~
selling_rna.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", S);
         ~~~~~^~~~~~~~~
selling_rna.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s%s", P, Q);
         ~~~~~^~~~~~~~~~~~~~