fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 1e5 + 5;
  5. const int BLOCK = 320;
  6.  
  7. int n, q;
  8. int a[MAXN], lazy[BLOCK], belong[MAXN], S, so_block;
  9. vector<pair<int, int>> block[BLOCK];
  10.  
  11. void rebuild(int b) {
  12.     block[b].clear();
  13.     int l = b * S;
  14.     int r = min(n, (b + 1) * S - 1);
  15.     for (int i = l; i <= r; ++i)
  16.         block[b].emplace_back(a[i], i);
  17.     sort(block[b].begin(), block[b].end());
  18. }
  19.  
  20. void update(int l, int r, int x) {
  21.     int bl = belong[l], br = belong[r];
  22.     if (bl == br) {
  23.         for (int i = l; i <= r; ++i) a[i] += x;
  24.         rebuild(bl);
  25.     } else {
  26.         for (int i = l; i <= (bl + 1) * S - 1; ++i) a[i] += x;
  27.         for (int i = br * S; i <= r; ++i) a[i] += x;
  28.         rebuild(bl);
  29.         rebuild(br);
  30.         for (int b = bl + 1; b < br; ++b)
  31.             lazy[b] += x;
  32.     }
  33. }
  34.  
  35. int query(int x) {
  36.     int trai = n + 1, phai = -1;
  37.     for (int b = 0; b < so_block; ++b) {
  38.         int val = x - lazy[b];
  39.         auto &v = block[b];
  40.         auto it = lower_bound(v.begin(), v.end(), make_pair(val, -1));
  41.         while (it != v.end() && it->first == val) {
  42.             trai = min(trai, it->second);
  43.             phai = max(phai, it->second);
  44.             ++it;
  45.         }
  46.     }
  47.     if (phai == -1) return -1;
  48.     return phai - trai;
  49. }
  50.  
  51. int main() {
  52.     ios_base::sync_with_stdio(false);
  53.     cin.tie(nullptr);
  54.  
  55.     cin >> n >> q;
  56.     S = sqrt(n) + 1;
  57.     so_block = (n + S - 1) / S;
  58.  
  59.     for (int i = 0; i < n; ++i) {
  60.         cin >> a[i];
  61.         belong[i] = i / S;
  62.     }
  63.     for (int b = 0; b < so_block; ++b)
  64.         rebuild(b);
  65.  
  66.     while (q--) {
  67.         int type;
  68.         cin >> type;
  69.         if (type == 1) {
  70.             int l, r, x;
  71.             cin >> l >> r >> x;
  72.             --l; --r;
  73.             update(l, r, x);
  74.         } else {
  75.             int x;
  76.             cin >> x;
  77.             cout << query(x) << '\n';
  78.         }
  79.     }
  80. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yETlm7
https://m...content-available-to-author-only...j.com/problem/383
language:
C++14 (gcc 8.3)
created:
9 hours 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!