fork download
copy 
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. typedef long long ll;
  8.  
  9. const int N = 500010, G = 1010;
  10. int n, q, koren;
  11. ll a[N], d[N];
  12. pair<ll, int> pa[G][G];
  13.  
  14. int grupa(int x)
  15. {
  16.     return 1 + (x - 1) / koren;
  17. }
  18.  
  19. void sortirajgrupu(int grp, int neki)
  20. {
  21.     int vel = 0;
  22.     for (int i = neki; i && grupa(i) == grp; i--) pa[grp][++vel] = {a[i], i};
  23.     for (int i = neki + 1; i <= n && grupa(i) == grp; i++) pa[grp][++vel] = {a[i], i};
  24.     sort(pa[grp] + 1, pa[grp] + vel + 1);
  25. }
  26.  
  27. int main()
  28. {
  29.     scanf("%d %d", &n, &q);
  30.     koren = sqrt(n);
  31.     for (int i = 1; i <= n; i++) scanf("%I64d", &a[i]);
  32.     for (int i = 1, g = 1; g <= n; i++, g += koren) sortirajgrupu(i, g);
  33.     while (q--)
  34.     {
  35.         int t;
  36.         scanf("%d", &t);
  37.         if (t == 1)
  38.         {
  39.             int l, r, x;
  40.             scanf("%d %d %d", &l, &r, &x);
  41.             int p = grupa(l), q = grupa(r);
  42.             if (p == q)
  43.             {
  44.                 for (int i = l; i <= r; i++) a[i] += x;
  45.                 sortirajgrupu(p, l);
  46.                 continue;
  47.             }
  48.             for (int i = l; i <= n && grupa(i) == p; i++) a[i] += x;
  49.             for (int i = r; i && grupa(i) == q; i--) a[i] += x;
  50.             sortirajgrupu(p, l);
  51.             sortirajgrupu(q, r);
  52.             for (int i = p + 1; i < q; i++) d[i] += x;
  53.         } else
  54.         {
  55.             int x, mi = 0, ma;
  56.             scanf("%d", &x);
  57.             for (int i = 1, g = 1; g <= n; i++, g += koren)
  58.             {
  59.                 int gor = min(n, g + koren - 1), vel = gor - g + 1;
  60.                 int pos = lower_bound(pa[i] + 1, pa[i] + vel + 1, pair<ll, int>(x - d[i], 1)) - pa[i];
  61.                 if (pos <= vel && pa[i][pos].first == x - d[i])
  62.                 {
  63.                     mi = pa[i][pos].second;
  64.                     break;
  65.                 }
  66.             }
  67.             for (int i = (n + koren - 1) / koren, g = (i - 1) * koren + 1; i; i--, g -= koren)
  68.             {
  69.                 int gor = min(n, g + koren - 1), vel = gor - g + 1;
  70.                 int pos = lower_bound(pa[i] + 1, pa[i] + vel + 1, pair<ll, int>(x - d[i] + 1, 1)) - pa[i] - 1;
  71.                 if (pos && pa[i][pos].first == x - d[i])
  72.                 {
  73.                     ma = pa[i][pos].second;
  74.                     break;
  75.                 }
  76.             }
  77.             if (mi) printf("%d\n", ma - mi); else
  78.             printf("-1\n");
  79.         }
  80.     }
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0s 22864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9WEbNP
language:
C++14 (gcc 8.3)
created:
9 years 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!