fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int Q = 25e4 + 5; 
  12. const int MX = 1e6 + 5; 
  13.  
  14. struct Node {
  15. 	int nxt[26]; 
  16. 	int cnt = 0; // trie[v].cnt = Số xâu đi qua đỉnh v hay nói cách khác là nhận xâu s tương ứng với v làm prefix 
  17. 	int mark = -1;  
  18.  
  19. 	Node() {
  20. 		memset(nxt, -1, sizeof nxt); 
  21. 	}
  22. }; 
  23.  
  24. int sz; 
  25. Node trie[MX]; 
  26.  
  27. void addString(const string& s, int i) {
  28. 	int v = 0; 
  29. 	trie[v].cnt++; 
  30.  
  31. 	for (char ch : s) {
  32. 		int c = ch - 'a'; 
  33. 		if (trie[v].nxt[c] == -1) {
  34. 			trie[v].nxt[c] = ++sz; 
  35. 		}
  36. 		v = trie[v].nxt[c]; 
  37. 		trie[v].cnt++; 
  38. 	}
  39.  
  40. 	trie[v].mark = i; 
  41. }
  42.  
  43. // Tìm đỉnh v tương ứng với xâu s trong cây trie
  44. int findV(const string& s) {
  45. 	int v = 0;  
  46.  
  47. 	for (char ch : s) {
  48. 		int c = ch - 'a';  
  49. 		int nxt_v = trie[v].nxt[c]; 
  50. 		if (nxt_v == -1) return -1; 
  51. 		v = nxt_v;		
  52. 	}
  53.  
  54. 	return v; 
  55. }
  56.  
  57. void removeString(const string& s) {
  58. 	int v = 0 ;   
  59. 	trie[v].cnt--; 
  60.  
  61. 	for (char ch : s) {
  62. 		int c = ch - 'a'; 
  63. 		v = trie[v].nxt[c]; 
  64. 		trie[v].cnt--; 
  65. 	}
  66.  
  67. 	trie[v].mark = -1; 
  68. }
  69.  
  70. int findKth(const string& s, int k) {
  71. 	int v = findV(s);
  72. 	if (v == -1 || trie[v].cnt < k) return -1;  
  73.  
  74. 	while (true) {
  75. 		if (k == 1 && trie[v].mark != -1) break;  
  76. 		k -= (trie[v].mark != -1);  
  77.  
  78. 		for (int c = 0; c <= 25; c++) {
  79. 			int nxt_v = trie[v].nxt[c]; 
  80. 			if (nxt_v == -1) continue; 
  81.  
  82. 			if (k <= trie[nxt_v].cnt) {
  83. 				v = nxt_v; 
  84. 				break; 
  85. 			}
  86. 			else {
  87. 				k -= trie[nxt_v].cnt; 
  88. 			}
  89. 		}
  90. 	}
  91.  
  92. 	return trie[v].mark; 
  93. }
  94.  
  95. int q; 
  96. string s[Q]; 
  97. bool removed[Q]; 
  98.  
  99. int main() {
  100. 	ios::sync_with_stdio(false); 
  101. 	cin.tie(nullptr); 	
  102. 	cin >> q; 
  103. 	for (int i = 1; i <= q; i++) {
  104. 		string type; cin >> type; 
  105.  
  106. 		if (type == "POST") {
  107. 			int x; char c; 
  108. 			cin >> x >> c; 
  109. 			s[i] = s[x] + c; 
  110. 			addString(s[i], i);
  111. 		}
  112.  
  113. 		if (type == "DELETE") {
  114. 			int x; cin >> x; 
  115. 			if (removed[x]) continue; 
  116. 			removeString(s[x]);
  117. 			removed[x] = true; 
  118. 		}
  119.  
  120. 		if (type == "GET") {
  121. 			string s; int k; 
  122. 			cin >> s >> k; 
  123. 			int ans = findKth(s, k); 
  124. 			cout << (ans == -1 ? 404 : ans) << '\n'; 
  125. 		}
  126. 	}
  127. }
Success #stdin #stdout 0.03s 120816KB
comments (?)
stdin
copy 
13
POST 0 l
POST 1 m
POST 2 a
POST 3 o
POST 1 o
POST 5 l
POST 3 i
POST 3 u
GET lmao 1
GET lmao 2
GET lma 2
DELETE 7
GET lma 2
stdout
copy 
4
404
7
4
https://ideone.com/EVC17H
language:
C++14 (gcc 8.3)
created:
1 year 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!