fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12. #define fbo find_by_order
  13. #define ook order_of_key
  14.  
  15. typedef long long ll;
  16. typedef pair<ll,ll> ii;
  17. typedef vector<int> vi;
  18. typedef long double ld; 
  19. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  20. typedef set<int>::iterator sit;
  21. typedef map<int,int>::iterator mit;
  22. typedef vector<int>::iterator vit;
  23.  
  24. const int MAXN = 1000001;
  25. const int sigma = 26;
  26.  
  27. int to[MAXN][sigma];
  28. int sz;
  29. int dp[MAXN];
  30. int term[MAXN];
  31.  
  32. void add_str(string &s)
  33. {
  34.     int cur = 0;
  35.     for(int i = 0; i < s.length(); i++)
  36.     {
  37. 		char c = s[i];
  38.         if(!to[cur][c - 'a'])
  39.         {
  40.             to[cur][c - 'a'] = sz++;
  41.         }
  42.         cur = to[cur][c - 'a'];
  43.     }
  44.     term[cur]++;
  45. }
  46.  
  47. void reset(int u)
  48. {
  49. 	sz=1;term[u]=0;
  50. 	for(int i = 0; i < sigma; i++)
  51. 	{
  52. 		if(to[u][i])
  53. 		{
  54. 			int z = to[u][i];
  55. 			to[u][i]=0;
  56. 			reset(z);
  57. 		}
  58. 	}
  59. }
  60.  
  61. int prefix(string &s)
  62. {
  63. 	int cur = 0;
  64. 	int cnt=0;
  65.     for(int i = 0; i < s.length(); i++)
  66.     {
  67. 		char c = s[i];
  68. 		cnt+=term[cur];
  69. 		//cerr<<i<<' '<<c<<' '<<cnt<<' '<<to[cur][c-'a']<<'\n';
  70.         if(!to[cur][c - 'a'])
  71.         {
  72. 			return cnt;
  73. 		}
  74. 		cur=to[cur][c-'a'];
  75. 	}
  76. 	cnt+=term[cur];
  77. 	return cnt;
  78. }
  79.  
  80. string a[100001];
  81. vector<pair<vector<string>, int> > vec;
  82. int ans[100001];
  83. int main()
  84. {
  85. 	ios_base::sync_with_stdio(0); cin.tie(0);
  86. 	sz=1;
  87. 	int n; cin>>n;
  88. 	for(int i = 0; i < n; i++)
  89. 	{
  90. 		cin>>a[i];
  91. 	}
  92. 	int q; cin>>q;
  93. 	vec.resize(q);
  94. 	for(int i = 0; i < q; i++)
  95. 	{
  96. 		int m,c;
  97. 		cin>>m>>c;
  98. 		vec[i].se=c;
  99. 		for(int j = 0;j<m;j++)
  100. 		{
  101. 			string s;cin>>s;
  102. 			vec[i].fi.pb(s);
  103. 		}
  104. 	}
  105. 	memset(ans,-1,sizeof(ans));
  106. 	deque<pair<ii,vi> > dq;
  107. 	vi ve2c;
  108. 	for(int i = 0; i<q;i++) ve2c.pb(i);
  109. 	dq.pb(mp(mp(1,n+1),ve2c));
  110. 	int ptr=0;
  111. 	while(!dq.empty())
  112. 	{
  113. 		int l=dq.front().fi.fi; int r=dq.front().fi.se;
  114. 		int mid=(l+r)>>1;
  115. 		if(l==r)
  116. 		{
  117. 			if(l>n)
  118. 			{
  119. 				dq.pop_front();
  120. 				continue;
  121. 			}
  122. 			for(int i = 0; i < dq.front().se.size(); i++)
  123. 			{
  124. 				ans[dq.front().se[i]]=l;
  125. 			}
  126. 			dq.pop_front();
  127. 			continue;
  128. 		}
  129. 		if(ptr>=mid)
  130. 		{
  131. 			ptr=0;
  132. 			reset(0);
  133. 		}
  134. 		while(ptr<mid)
  135. 		{
  136. 			add_str(a[ptr]);
  137. 			ptr++;
  138. 		}
  139. 		vi L,R;
  140. 		for(int i = 0; i < dq.front().se.size(); i++)
  141. 		{
  142. 			int u = dq.front().se[i];
  143. 			ll ct = 0;
  144. 			for(int j = 0; j < vec[u].fi.size(); j++)
  145. 			{
  146. 				ll x=prefix(vec[u].fi[j]);
  147. 				ct+=x;
  148. 			//	cerr<<u<<' '<<mid<<' '<<vec[u].fi[j]<<' '<<x<<'\n';
  149. 				if(ct>=vec[u].se) break;
  150. 			}
  151. 			//cerr<<u<<' '<<mid<<' '<<ct<<' '<<vec[u].se<<'\n';
  152. 			if(ct>=vec[u].se)
  153. 			{
  154. 				L.pb(u);
  155. 			}
  156. 			else
  157. 			{
  158. 				R.pb(u);
  159. 			}
  160. 		}
  161. 		dq.pop_front();
  162. 		dq.push_back(mp(mp(l,mid),L));
  163. 		dq.pb(mp(mp(mid+1,r),R));
  164. 	}
  165. 	for(int i = 0; i < q; i++)
  166. 	{
  167. 		cout<<ans[i]<<'\n';
  168. 	}
  169. }
  170.  
Runtime error #stdin #stdout #stderr 1.82s 114624KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/UIwYRu
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!