fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair <int, int>
  4. #define mp make_pair
  5. #define F first
  6. #define S second
  7. #define ll long long
  8. #define iosbase ios_base::sync_with_stdio(false)
  9. #define sc scanf
  10. #define pr printf
  11. #define null NULL
  12. #define getcx getchar_unlocked
  13. #define lb lower_bound
  14. #define ub upper_bound
  15. #define all(x) x.begin(), x.end()
  16. #define pll pair<ll,ll>
  17. #define vi vector <int>
  18. #define vll vector <ll>
  19.  
  20. #define maxs 100005
  21. #define logmaxs 35
  22.  
  23. #define MOD 1000000007
  24. #define eps 1e-9
  25. #define llmax 1e15+5
  26. #define intmax 1e9+5
  27. #define intmin -intmax
  28.  
  29. #define pi 3.14159265358979
  30.  
  31. using namespace std;
  32.  
  33. map <int, int> ans[maxs];
  34.  
  35. string s;
  36. vector <string> v;
  37. int mrk[maxs];
  38.  
  39. struct trie{
  40. 	int edge[26];
  41. 	int prefix;
  42. };
  43.  
  44. trie tree[maxs];
  45. int cnt;
  46.  
  47. void insert(int node, int idx){
  48. 	if(idx==s.size()){
  49. 		tree[node].prefix++;
  50. 		ans[idx][tree[node].prefix]++;
  51. 		return ;
  52. 	}
  53. 	int x=s[idx]-'a';
  54. 	tree[node].prefix++;
  55. 	ans[idx][tree[node].prefix]++;
  56. 	if(tree[node].edge[x]!=0){
  57. 		insert(tree[node].edge[x], idx+1);
  58. 	}
  59. 	else{
  60. 		++cnt;
  61. 		tree[node].edge[x]=cnt;
  62. 		insert(tree[node].edge[x], idx+1);
  63. 	}
  64. }
  65.  
  66. void remove(int node, int idx){
  67. 	if(idx==s.size()){
  68. 	    ans[idx][tree[node].prefix]--;
  69. 		tree[node].prefix--;
  70. 		return ;
  71. 	}
  72. 	remove(tree[node].edge[s[idx]-'a'], idx+1);
  73. 	ans[idx][tree[node].prefix]--;
  74. 	tree[node].prefix--;
  75. 	int x=tree[node].edge[s[idx]-'a'];
  76. 	if(tree[x].prefix==0)
  77. 		tree[node].edge[s[idx]-'a']=0;
  78. }
  79.  
  80. int main(){
  81. 	iosbase;
  82. 	int q,t,k,l,x;
  83. 	cin>>q;
  84. 	for(int i=0; i<q; i++){
  85. 		cin>>t;
  86. 		if(t==1){
  87. 			cin>>s;
  88. 			reverse(s.begin(), s.end());
  89. 			v.pb(s);
  90. 			mrk[v.size()]=1;
  91. 			insert(0, 0);
  92. 		}
  93. 		else if(t==2){
  94. 			v.pb("");
  95. 			cin>>k>>l;
  96. 			if(ans[l][k])
  97. 			cout<<"YES"<<endl;
  98. 			else cout<<"NO"<<endl;
  99. 		}
  100. 		else {
  101. 			v.pb("");
  102. 			cin>>x;
  103. 			if(!mrk[x])
  104. 			continue;
  105. 			s=v[x-1];
  106. 			mrk[x]=0;
  107. 			remove(0, 0);
  108. 		}
  109. 	}
  110. 	return 0;
  111. }
  112.  
Runtime error #stdin #stdout 0s 16752KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Y3Zgqg
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!