#include <bits/stdc++.h>
#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=2e5+9;
int id[500],sus=0;
struct Trie{
struct Node{
Node* child[4];
int exist, cnt,mini=-1;
Node() {
for (int i = 0; i < 4; i++) child[i] = NULL;
exist = cnt = 0;
}
};
int cur;
Node* root;
Trie() : cur(0) {
root = new Node();
};
void add_string(string s,int ind=0) {
Node* p = root;
for (auto f : s) {
int c = id[f];
if (p->child[c] == NULL) p->child[c] = new Node();
p = p->child[c];
if (ind) {
if (p->mini==-1) p->mini=ind;
else p->mini=min(p->mini,ind);
}
p->cnt++;
}
p->exist++;
}
bool delete_string_recursive(Node* p, string& s, int i) {
if (i != (int)s.size()) {
int c = id[s[i]];
bool isChildDeleted = delete_string_recursive(p->child[c], s, i + 1);
if (isChildDeleted) p->child[c] = NULL;
}
else p->exist--;
if (p != root) {
p->cnt--;
if (p->cnt == 0) {
delete(p);
return true;
}
}
return false;
}
void delete_string(string s) {
if (find_string(s) == false) return;
delete_string_recursive(root, s, 0);
}
bool find_string(string s) {
Node* p = root;
for (auto f : s) {
int c = id[f];
if (p->child[c] == NULL) return false;
p = p->child[c];
}
return (p->exist != 0);
}
pair<int,int> get(string s) {
Node* p = root;
for (auto f : s) {
int c = id[f];
if (p->child[c] == NULL) return mpa(-1,-1);
p = p->child[c];
}
return mpa(p->mini,p->mini+p->cnt-1);
}
int getnum(string s) {
Node* p = root;
for (auto f : s) {
int c = id[f];
if (p->child[c] == NULL) return 0;
p = p->child[c];
}
return p->cnt;
}
};
ll hilOrd(int x, int y, int pow, int rotate) {
if (x<0 || y<0) return 2LL*1e18;
if (pow == 0) return 0;
int hpow = 1 << (pow-1);
int seg = (x < hpow) ? ((y < hpow) ? 0 : 3) : ((y < hpow) ? 1 : 2);
seg = (seg + rotate) & 3;
const int rotateDelta[4] = {3, 0, 0, 1};
int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
int nrot = (rotate + rotateDelta[seg]) & 3;
ll subSquareSize = int64_t(1) << (2*pow - 2);
ll ans = seg * subSquareSize;
ll add = hilOrd(nx, ny, pow-1, nrot);
ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
return ans;
}
struct query {
int l,r,ind;
ll order=0;
string p,q;
void calOrd() {
order=hilOrd(l,r,20,0);
}
};
bool isPrefix(string &s,string s1) {
if (sz(s)<sz(s1)) return 0;
For(i,0,sz(s1)-1) if (s[i]!=s1[i]) return 0;
return 1;
}
Trie trie,trie1;
query qr[N];
string a[N],a1[N];
int n,m,ans[N],tmp=0;
int main() {
cin.tie(0)->sync_with_stdio(0);
id['C']=0,id['U']=1,id['G']=2,id['A']=3;
freopen("D.INP","r",stdin);
freopen("D.OUT","w",stdout);
cin >> n >> m;
For(i,1,n) cin >> a[i];
sort(a,a+1+n);
For(i,1,n) {
a1[i]=a[i];
reverse(all(a1[i]));
}
For(i,1,n) trie.add_string(a[i],i);
For(i,1,m) {
cin >> qr[i].p >> qr[i].q;
reverse(all(qr[i].q));
qr[i].ind=i;
pair<int,int> sus=trie.get(qr[i].p);
qr[i].l=sus.ff;
qr[i].r=sus.ss;
qr[i].calOrd();
}
sort(qr+1,qr+1+m,[](const query &A, const query &B) {
return A.order<B.order;
});
fill(ans,ans+1+n,0);
int l=qr[1].l,r=qr[1].r;
For(i,qr[1].l,qr[1].r) {
if (i<0) break;
trie1.add_string(a1[i]);
}
if (qr[1].l>0 && qr[1].r>0) ans[qr[1].ind]=trie1.getnum(qr[1].q);
For(i,2,m) {
if (qr[i].l<0 || qr[i].r<0) break;
if (l>qr[i].l) For(j,qr[i].l,l-1) trie1.add_string(a1[j]);
if (r<qr[i].r) For(j,r+1,qr[i].r) trie1.add_string(a1[j]);
if (l<qr[i].l) For(j,l,qr[i].l-1) trie1.delete_string(a1[j]);
if (r>qr[i].l) For(j,qr[i].r+1,r) trie1.delete_string(a1[j]);
l=qr[i].l,r=qr[i].r;
ans[qr[i].ind]=trie1.getnum(qr[i].q);
}
For(i,1,m) cout << ans[i] << endl;
return 0;
}
Compilation message
selling_rna.cpp: In member function 'void Trie::add_string(std::string, int)':
selling_rna.cpp:52:24: warning: array subscript has type 'char' [-Wchar-subscripts]
52 | int c = id[f];
| ^
selling_rna.cpp: In member function 'bool Trie::delete_string_recursive(Trie::Node*, std::string&, int)':
selling_rna.cpp:65:28: warning: array subscript has type 'char' [-Wchar-subscripts]
65 | int c = id[s[i]];
| ^
selling_rna.cpp: In member function 'bool Trie::find_string(std::string)':
selling_rna.cpp:90:24: warning: array subscript has type 'char' [-Wchar-subscripts]
90 | int c = id[f];
| ^
selling_rna.cpp: In member function 'std::pair<int, int> Trie::get(std::string)':
selling_rna.cpp:99:24: warning: array subscript has type 'char' [-Wchar-subscripts]
99 | int c = id[f];
| ^
selling_rna.cpp: In member function 'int Trie::getnum(std::string)':
selling_rna.cpp:108:24: warning: array subscript has type 'char' [-Wchar-subscripts]
108 | int c = id[f];
| ^
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:152:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | freopen("D.INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
selling_rna.cpp:153:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen("D.OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
30812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
30808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
30808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
30812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
