fork download
copy 
  1. ///HBTN
  2. #include <bits/stdc++.h>
  3. #define int long long
  4. #define N (int) 1e6 + 5
  5. #define acceleration ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6.  
  7. using namespace std;
  8.  
  9. int n, m, q, res = 0;
  10. int a[N], T[4 * N], P[4 * N];
  11.  
  12.  
  13. void update(int id, int l, int r, int pos, int val)
  14. {
  15.     if(pos < l || pos > r) return;
  16.     if(l == r)
  17.     {
  18.         T[id] = val;
  19.         P[id] = val;
  20.         a[pos] = val;
  21.         return;
  22.     }
  23.  
  24.     int mid = (l + r) >> 1;
  25.     update(id * 2, l, mid, pos, val);
  26.     update(id * 2 + 1, mid + 1, r, pos, val);
  27.  
  28.     T[id] = min(T[id * 2], T[id * 2 + 1]);
  29.     P[id] = max(P[id * 2], P[id * 2 + 1]);
  30. }
  31.  
  32. int get(int id, int l, int r, int u, int v)
  33. {
  34.     if(v < l || u > r) return 1e18;
  35.     if(u <= l && v >= r) return T[id];
  36.  
  37.     int mid = (l + r) >> 1;
  38.     int t1 = get(id * 2, l, mid, u, v);
  39.     int t2 = get(id * 2 + 1, mid + 1, r, u, v);
  40.  
  41.     return min(t1, t2);
  42. }
  43.  
  44. int get_max(int id, int l, int r, int u, int v)
  45. {
  46.     if(v < l || u > r) return -1e18;
  47.     if(u <= l && v >= r) return P[id];
  48.  
  49.  
  50.     int mid = (l + r) >> 1;
  51.     int t1 = get_max(id * 2, l, mid, u, v);
  52.     int t2 = get_max(id * 2 + 1, mid + 1, r, u, v);
  53.  
  54.     return max(t1, t2);
  55. }
  56.  
  57. signed main()
  58. {
  59.     acceleration
  60.     #define TASK "HBTN"
  61.     if(fopen(TASK".INP","r"))
  62.     {
  63.         freopen(TASK".INP", "r", stdin);
  64.         freopen(TASK".OUT", "w", stdout);
  65.     }
  66.     cin >> n >> m;
  67.     for(int i = 1; i <= n; i++)
  68.     {
  69.         cin >> a[i];
  70.         update(1, 1, n, i, a[i]);
  71.     }
  72.  
  73.     while(m--)
  74.     {
  75.         int x, y, type; cin >> type >> x >> y;
  76.         if(type == 1)
  77.         {
  78.             int tmp_x = a[x];
  79.             int tmp_y = a[y];
  80.             update(1, 1, n, x, tmp_y);
  81.             update(1, 1, n, y, tmp_x);
  82.         }
  83.         else
  84.         {
  85.             int Min = get(1, 1, n, x, y);
  86.             int Max = get_max(1, 1, n, x, y);
  87.  
  88.             if(Max - Min == y - x) cout << "YES\n";
  89.             else cout << "NO\n";
  90.         }
  91.     }
  92.  
  93.  
  94.  
  95. }
  96.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/kkaB7q
language:
C++ (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!