Advertisement
K_Y_M_bl_C

Untitled

Sep 17th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.87 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef vector<int> vi;
  7. typedef pair<int, int> pii;
  8.  
  9. #define ff first
  10. #define ss second
  11. #define y1 y111
  12. #define X first
  13. #define Y second
  14. #define mk make_pair
  15. #define inb push_back
  16. #define all(v) v.begin(), v.end()
  17.  
  18. const int MAXN = (int)1e6 + 9, MAXN1 = (int)2e4 + 7;
  19. const int INFint = (int)1e9 + 7, P = 31;
  20. const ll INFll = (ll)1e18 + 7, MOD = (ll)1e9 + 7;
  21. const double INFfl = 1e18 * 4 + 7;
  22. const double EPS = 1e-7;
  23. const double PI = atan2(0, -1);
  24.  
  25. int solve();
  26.  
  27. int main()
  28. {
  29. #define TASK ""
  30. #ifdef _DEBUG
  31.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  32. #else
  33.     //freopen(TASK".in", "r", stdin), freopen(TASK".out", "w", stdout);
  34. #endif
  35.     solve();
  36. }
  37.  
  38. const int STRBUF = (int)1e6 + 7;
  39. char buf[STRBUF];
  40. string get_str()
  41. {
  42.     scanf(" %s", buf);
  43.     return string(buf);
  44. }
  45.  
  46. int solve()
  47. {
  48.     int n, m;
  49.     scanf("%d %d", &n, &m);
  50.     vi d(n), a(n);
  51.     for (int i = 0; i < n; ++i)
  52.         scanf("%d", &d[i]), --d[i];
  53.     for (int i = 0; i < m; ++i)
  54.         scanf("%d", &a[i]);
  55.     int l = -1, r = n;
  56.     auto check = [&](int x)
  57.     {
  58.         vector<pii> lst(m, mk(-1, 0));
  59.         for (int i = 0; i < m; ++i)
  60.             lst[i].Y = i;
  61.         for (int i = 0; i < x; ++i)
  62.         {
  63.             if (d[i] != -1)
  64.                 lst[d[i]].X = i;
  65.         }
  66.         sort(all(lst));
  67.         if (lst[0].X == -1)
  68.             return 0;
  69.         int bds = 0;
  70.         for (int i = 0; i < m; ++i)
  71.         {
  72.             int id = lst[i].Y;
  73.             if (bds + a[id] <= lst[i].X)
  74.                 bds += a[id] + 1;
  75.             else
  76.                 return 0;
  77.         }
  78.         return 1;
  79.     };
  80.     while (r - l > 1)
  81.     {
  82.         int mid = l + r >> 1;
  83.         if (check(mid))
  84.             r = mid;
  85.         else
  86.             l = mid;
  87.     }
  88.     if (!check(r))
  89.         puts("-1"), exit(0);
  90.     printf("%d\n", r);
  91.     return 0;
  92. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement