Advertisement
kinhosz

code

Jul 26th, 2019
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define asp ""
  4. #define aps ''
  5. #define one 1
  6. #define two 2
  7. #define dif !=
  8. typedef pair<int,int> ii;
  9.  
  10. int main(){
  11.  
  12. ios::sync_with_stdio(0);
  13. cin.tie(0);
  14.  
  15. vector<set<ii>> Number(2600005); // 26x10^5
  16. vector<bool> ocup(2600005);
  17.  
  18. string s;
  19. cin >> s;
  20.  
  21. for(int i=0;i<2600005;i++) ocup[i] = false;
  22.  
  23. priority_queue<int,vector<int>,greater<int>> pq;
  24.  
  25. for(int i=0;i<s.size();i++){
  26. int valor = s[i] - 'a' + 1;
  27. Number[valor].insert({i,i}); // push nos ponteiros
  28. if(!ocup[valor]){
  29. pq.push(valor);
  30. ocup[valor] = true;
  31. }
  32. }
  33.  
  34. int cont = 0;
  35.  
  36. while(!pq.empty()){
  37.  
  38. int valor = pq.top();
  39. pq.pop();
  40. cont++;
  41.  
  42. for(auto &pointer: Number[valor]){
  43. int novo;
  44. if(pointer.first - 1 >= 0){
  45. novo = valor + s[pointer.first - 1] - 'a' + 1;
  46. Number[novo].insert({pointer.first - 1,pointer.second});
  47. if(!ocup[novo]){
  48. pq.push(novo);
  49. ocup[novo] = true;
  50. }
  51. }
  52. if(pointer.second + 1 < s.size()){
  53. novo = valor + s[pointer.second + 1] - 'a' + 1;
  54. Number[novo].insert({pointer.first,pointer.second + 1});
  55. if(!ocup[novo]){
  56. pq.push(novo);
  57. ocup[novo] = true;
  58. }
  59. }
  60. }
  61. }
  62.  
  63. cout << cont << endl;
  64. }
  65.  
  66. // abbab
  67. // adbbabdcdbcbacdabbaccdac
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement