fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. struct Node
  9. {
  10.     int max_g, min_f, lazy;
  11. };
  12.  
  13. const int maxn = 2e5;
  14. const int INF = 1e9;
  15.  
  16. int n, q, ans[maxn + 10];
  17. ll a[maxn + 10];
  18. vector<int> pos[maxn + 10];
  19. Node tree[4 * maxn + 10];
  20.  
  21. void push(int id, int l, int r)
  22. {
  23.     if (!tree[id].lazy)
  24.         return ;
  25.     int m = l + r >> 1;
  26.     tree[id << 1].lazy = tree[id << 1 | 1].lazy = tree[id].lazy;
  27.     tree[id << 1].max_g = tree[id << 1 | 1].max_g = tree[id].lazy;
  28.     tree[id << 1].min_f = l - tree[id].lazy + 1;
  29.     tree[id << 1 | 1].min_f = m - tree[id].lazy + 2;
  30.     tree[id].lazy = 0;
  31. }
  32. void update(int id, int l, int r, int u, int v, int val)
  33. {
  34.     if (r < u || l > v)
  35.         return ;
  36.     if (u <= l && r <= v)
  37.     {
  38.         tree[id].max_g = val;
  39.         tree[id].min_f = l - val + 1;
  40.         tree[id].lazy = val;
  41.         return ;
  42.     }
  43.     push(id, l, r);
  44.     int m = l + r >> 1;
  45.     update(id << 1, l, m, u, v, val);
  46.     update(id << 1 | 1, m + 1, r, u, v, val);
  47.     tree[id].max_g = max(tree[id << 1].max_g, tree[id << 1 | 1].max_g);
  48.     tree[id].min_f = min(tree[id << 1].min_f, tree[id << 1 | 1].min_f);
  49. }
  50. int walk(int id, int l, int r, int val)
  51. {
  52.     if (tree[id].max_g < val)
  53.         return 0;
  54.     if (l == r)
  55.         return l;
  56.     int m = l + r >> 1;
  57.     if (tree[id << 1].max_g >= val)
  58.         return walk(id << 1, l, m, val);
  59.     return walk(id << 1 | 1, m + 1, r, val);
  60. }
  61. void print_tree(int id, int l, int r)
  62. {
  63.     if (l == r)
  64.         return cout << tree[id].max_g << ' ', void();
  65.     int m = l + r >> 1;
  66.     push(id, l, r);
  67.     print_tree(id << 1, l, m);
  68.     print_tree(id << 1 | 1, m + 1, r);
  69. }
  70.  
  71. int main()
  72. {
  73.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  74.     if (fopen("DAYDAYDU.INP", "r"))
  75.     {
  76.         freopen("DAYDAYDU.INP", "r", stdin);
  77.         freopen("DAYDAYDU.OUT", "w", stdout);
  78.     }
  79.  
  80.     cin >> n >> q;
  81.     for (int i = 1; i <= n; i++)
  82.     {
  83.         cin >> a[i];
  84.         if (a[i] <= n)
  85.             pos[a[i]].push_back(i);
  86.     }
  87.     for (int i = 1; i <= 4 * n; i++)
  88.         tree[i].min_f = tree[i].max_g = INF;
  89.     for (int x = 1; x <= n; x++)
  90.     {
  91.         if (pos[x].empty())
  92.             break;
  93.         pos[x].push_back(n + 1);
  94. //        cout << x, el;
  95.         for (int i = 1; i < pos[x].size(); i++)
  96.         {
  97.             int min_pos = walk(1, 1, n, pos[x][i - 1]);
  98. //            cout << min_pos << ' ' << pos[x][i] - 1, el;
  99.             if (min_pos)
  100.                 update(1, 1, n, min_pos, pos[x][i] - 1, pos[x][i - 1]);
  101.         }
  102.         if (pos[x][0] > 1)
  103.             update(1, 1, n, 1, pos[x][0] - 1, -INF);
  104.         ans[x] = tree[1].min_f;
  105. //        print_tree(1, 1, n);
  106. //        el;
  107. //        el;
  108.     }
  109.     for (int i = 1; i <= q; i++)
  110.     {
  111.         int x;
  112.         cin >> x;
  113.         cout << (x <= n && ans[x] ? ans[x] : -1), el;
  114.     }
  115. }
Success #stdin #stdout 0.01s 11760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/rUd2o4
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

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!