Advertisement
Guest User

asd

a guest
Sep 22nd, 2014
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.43 KB | None | 0 0
  1. #include <cstdio>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. const int MAXN = 1000000 + 10;
  7. int n, k, m, l;
  8. int a[MAXN], x[MAXN], y[MAXN];
  9.  
  10. int indInX[MAXN], indInY[MAXN];
  11. int mostLeft[MAXN], mostRight[MAXN];
  12. int minSuf[MAXN];
  13. int left[MAXN], right[MAXN];
  14. int leftRes[MAXN], rightRes[MAXN];
  15.  
  16. int main()
  17. {
  18.     scanf("%d %d", &n, &k);
  19.     for (int i = 0; i < n; ++i)
  20.     {
  21.         scanf("%d", &a[i]);
  22.         --a[i];
  23.     }
  24.     scanf("%d %d", &m, &l);
  25.     for (int i = 0; i < m; ++i)
  26.     {
  27.         scanf("%d", &x[i]);
  28.         --x[i];
  29.     }
  30.     for (int i = 0; i < l; ++i)
  31.     {
  32.         scanf("%d", &y[i]);
  33.         --y[i];
  34.     }
  35.  
  36.  
  37.     for (int i = 0; i < k; ++i)
  38.         indInX[i] = indInY[i] = -1;
  39.     for (int i = 0; i < m; ++i)
  40.         indInX[x[i]] = i;
  41.     for (int i = 0; i < l; ++i)
  42.         indInY[y[i]] = i;
  43.    
  44.     for (int i = 0; i < k; ++i)
  45.         mostRight[i] = mostLeft[i] = -1;
  46.     for (int i = 0; i < n; ++i)
  47.     {
  48.         int idx = indInX[a[i]];
  49.         left[i] = -1;
  50.         if (idx > 0)
  51.             left[i] = mostRight[x[idx-1]];
  52.         mostRight[a[i]] = i;
  53.     }
  54.  
  55.     for (int i = n-1; i >= 0; --i)
  56.     {
  57.         int idy = indInY[a[i]];
  58.         right[i] = -1;
  59.         if (idy > 0)
  60.             right[i] = mostLeft[y[idy-1]];
  61.         mostLeft[a[i]] = i;
  62.     }
  63.     minSuf[0] = mostRight[a[0]];
  64.     for (int i = 1; i < n; ++i)
  65.     {
  66.         minSuf[i] = max(minSuf[i-1], mostRight[a[i]]);
  67.     }
  68.  
  69.     for (int i = 0; i < n; ++i)
  70.     {
  71.         int idx = indInX[a[i]];
  72.         leftRes[i] = -1;
  73.         if (idx == 0)
  74.         {
  75.             leftRes[i] = i;
  76.         }
  77.         else if (idx > 0 && left[i] != -1)
  78.         {
  79.             leftRes[i] = leftRes[left[i]];
  80.         }
  81.     }
  82.  
  83.     for (int i = n-1; i >= 0; --i)
  84.     {
  85.         int idy = indInY[a[i]];
  86.         rightRes[i] = -1;
  87.         if (idy == 0)
  88.         {
  89.             rightRes[i] = i;
  90.         }
  91.         else if (idy > 0 && right[i] != -1)
  92.         {
  93.             rightRes[i] = rightRes[right[i]];
  94.         }
  95.     }
  96.  
  97.     vector<int> res;
  98.     for (int i = 0; i < n; ++i)
  99.     {
  100.         if (a[i] == x[m-1])
  101.         {
  102.             int l = leftRes[i];
  103.             int r = rightRes[i];
  104.             if (l > 0 && r != -1 && minSuf[l-1] > r)
  105.                 res.push_back(i+1);
  106.         }
  107.     }
  108.     printf("%d\n", res.size());
  109.     for (int i = 0; i < res.size(); ++i)
  110.         printf("%d%c", res[i], " \n"[i+1==res.size()]);
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement