Advertisement
milon34

range_value_increase and value update with lazy propagation

Feb 17th, 2023 (edited)
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define ll long long int
  5. const int MAXN = 55;
  6.  
  7. int a[MAXN], lazy[4 * MAXN], segtree[4 * MAXN];
  8.  
  9. int merge(int a, int b) {
  10.     return max(a, b);
  11. }
  12.  
  13. void build(int idx, int l, int r) {
  14.     if (l == r) {
  15.         segtree[idx] = a[l];
  16.         return;
  17.     }
  18.     int m = (l + r) / 2;
  19.     build(idx * 2, l, m);
  20.     build(idx * 2 + 1, m + 1, r);
  21.     segtree[idx] = merge(segtree[idx * 2], segtree[idx * 2 + 1]);
  22. }
  23.  
  24. void apply_lazy(int idx, int l, int r) {
  25.     segtree[idx] += lazy[idx];
  26.     if (l != r) {
  27.         lazy[idx * 2] += lazy[idx];
  28.         lazy[idx * 2 + 1] += lazy[idx];
  29.     }
  30.     lazy[idx] = 0;
  31. }
  32.  
  33. void update(int idx, int l, int r, int ql, int qr, int val) {
  34.     if (lazy[idx] != 0) apply_lazy(idx, l, r);
  35.     if (ql > r || qr < l) return;
  36.     if (ql <= l && r <= qr) {
  37.         lazy[idx] += val;
  38.         apply_lazy(idx, l, r);
  39.         return;
  40.     }
  41.     int m = (l + r) / 2;
  42.     update(idx * 2, l, m, ql, qr, val);
  43.     update(idx * 2 + 1, m + 1, r, ql, qr, val);
  44.     segtree[idx] = merge(segtree[idx * 2], segtree[idx * 2 + 1]);
  45. }
  46.  
  47. int query(int idx, int l, int r, int ql, int qr) {
  48.     if (lazy[idx] != 0) apply_lazy(idx, l, r);
  49.     if (ql > r || qr < l) return 0;
  50.     if (ql <= l && r <= qr) return segtree[idx];
  51.     int m = (l + r) / 2;
  52.     return merge(query(idx * 2, l, m, ql, qr), query(idx * 2 + 1, m + 1, r, ql, qr));
  53. }
  54.  
  55. void up_pro(int idx, int l, int r, int ql, int qr, int val) {
  56.     if (lazy[idx] != 0) apply_lazy(idx, l, r);
  57.     if (ql > r || qr < l) return;
  58.     if (ql <= l && r <= qr) {
  59.         lazy[idx] = val;
  60.         apply_lazy(idx, l, r);
  61.         return;
  62.     }
  63.     int m = (l + r) / 2;
  64.     update(idx * 2, l, m, ql, qr, val);
  65.     update(idx * 2 + 1, m + 1, r, ql, qr, val);
  66.     segtree[idx] = merge(segtree[idx * 2], segtree[idx * 2 + 1]);
  67. }
  68.  
  69. int main() {
  70.     ios_base::sync_with_stdio(false);
  71.     cin.tie(0);
  72.     int tt;
  73.     cin >> tt;
  74.     while (tt--) {
  75.         int n, k;
  76.         cin >> n >> k;
  77.         build(1, 1, 50);
  78.         vector<pair<int, int>> vec;
  79.         for (int i = 0; i < n; i++) {
  80.             int l, r;
  81.             cin >> l >> r;
  82.             if (l <= k && k <= r) {
  83.                 vec.push_back({l, r});
  84.                 update(1, 1, 50, l, r, 1);
  85.             }
  86.         }
  87. //        for (int i = 0; i < n; i++) {
  88. //            int l = vec[i].first;
  89. //            int r = vec[i].second;
  90. //            if (l <= k && k <= r) {
  91. //                continue;
  92. //            }
  93. //            update(1, 1, 50, l, r, -1);
  94. //        }
  95.         int mx1 = query(1, 1, 50, k, k);
  96.         up_pro(1, 1, 50, k, k, -1);
  97.         int check = -1;
  98.         for (int i = 0; i < vec.size(); i++) {
  99.             int l = vec[i].first;
  100.             int r = vec[i].second;
  101.             check = max(check, query(1, 1, 50, l, r));
  102.         }
  103. //        cout << mx1 << " " << check << endl;
  104.         if (mx1 > check && check != -1) {
  105.             cout << "YES" << '\n';
  106.         } else {
  107.             cout << "NO" << '\n';
  108.         }
  109.         memset(a, 0, sizeof(a));
  110.         memset(lazy, 0, sizeof(lazy));
  111.         memset(segtree, 0, sizeof(segtree));
  112.  
  113.  
  114.     }
  115.     return 0;
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement