Advertisement
999ms

Untitled

Mar 3rd, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.08 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5.  
  6. int main(){
  7. ios_base::sync_with_stdio(false);cin.tie(nullptr);
  8. int m,k,n,s;
  9. cin>>m>>k>>n>>s;
  10. int a[m];
  11. for(int i=0;i<m;i++){
  12. cin>>a[i];
  13. }
  14. int b[s];
  15. for(int i=0;i<s;i++){
  16. cin>>b[i];
  17. }
  18. int delta = m - n * k;
  19. map<int,int> good;
  20. for(int i=0;i<s;i++){
  21. good[b[i]]++;
  22. }
  23. map<int,int> cur;
  24. for(int i = 0; i < delta + k - 1; i++){
  25. cur[a[i]]++;
  26. }
  27. int curVal = 0;
  28. for(auto [v, q] : good){
  29. if(cur[v] >= q){
  30. curVal++;
  31. }
  32. }
  33. int needSize = good.size();
  34. vector<int> v;
  35.  
  36. for(int i = delta + k -1; i < m ;i++){
  37. cur[a[i]]++;
  38. if(cur[a[i]]==good[a[i]]){
  39. curVal++;
  40. }
  41. if(curVal==needSize){
  42. v.push_back(i - delta - k + 1);
  43. }
  44. cur[a[i - delta - k + 1]]--;
  45. if(cur[a[i - delta - k +1 ]] + 1 == good[a[i -delta - k + 1]]) curVal--;
  46. }
  47.  
  48. for(int i : v){
  49. if(i%k==0){
  50. bool del[delta + k] = {false};
  51. multiset<int> Set;
  52. for(int j=i;j<delta+k+i;j++){
  53. Set.insert(a[j]);
  54. }
  55. for(auto [v,q] : good){
  56. while(q--){
  57. Set.extract(v);
  58. }
  59. }
  60. int curActive = s;
  61. while(curActive<k){
  62. Set.extract(Set.begin());
  63. curActive++;
  64. }
  65. for(int j=i;j<delta+k+i;j++){
  66. if(Set.find(a[j])!=Set.end()){
  67. del[j-i] = true;
  68. Set.extract(a[j]);
  69. }
  70. }
  71. vector<int> ans;
  72. for(int j = i; j<delta + k + i; j++){
  73. if(del[j-i]){
  74. ans.push_back(j+1);
  75. }
  76. }
  77. cout<<ans.size()<<endl;
  78. for(int i : ans){
  79. cout<<i<<" ";
  80. }
  81. return 0;
  82. }
  83. }
  84. cout<<-1;
  85. return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement