Advertisement
wym1111

Untitled

Oct 22nd, 2023
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5. #define endl '\n'
  6. const int N = 1e5 + 10;
  7.  
  8. int n, m;
  9. struct str {
  10.     ll l, r;
  11.     bool operator < (const str & tmp) const {
  12.         return r > tmp.r;
  13.     }
  14. } seg[N];
  15.  
  16. map<ll, int> id;
  17. int cnt = 0;
  18.  
  19. struct Node{
  20.     int mx, add;
  21. } node[N << 3];
  22.  
  23. void pushup (int p) {
  24.     node[p].mx = max (node[p << 1].mx, node[p << 1 | 1].mx);
  25. }
  26. void build (int s, int t, int p) {
  27.     node[p].add = 0;
  28.     if (s == t) {
  29.         node[p].mx = 0;
  30.         return;
  31.     }
  32.     int mid = (s + t) >> 1;
  33.     build(s, mid, p << 1);
  34.     build(mid + 1, t, p << 1 | 1);
  35.     pushup(p);
  36. }
  37. void pushdown(int p) {
  38.     if (node[p].add) {
  39.         node[p << 1].add += node[p].add;
  40.         node[p << 1].mx += node[p].add;
  41.         node[p << 1 | 1].add += node[p].add;
  42.         node[p << 1 | 1].mx += node[p].add;
  43.         node[p].add = 0;
  44.     }
  45. }
  46. void update (int s, int t, int l, int r, int p, int v) {
  47.     if (l <= s && t <= r) {
  48.         node[p].mx += v;
  49.         node[p].add += v;
  50.         return;
  51.     }
  52.     pushdown(p);
  53.     int mid = (s + t) >> 1;
  54.     if (l <= mid) update(s, mid, l, r, p << 1, v);
  55.     if (mid < r) update(mid + 1, t, l, r, p << 1 | 1, v);
  56.     pushup(p);
  57. }
  58. int query (int s, int t, int l, int r, int p) {
  59.     if (l <= s && t <= r) return node[p].mx;
  60.     pushdown(p);
  61.     int mid = (s + t) >> 1;
  62.     int res = 0;
  63.     if (l <= mid) res = query(s ,mid, l, r, p << 1);
  64.     if (mid < r) res = max (res, query(mid + 1, t, l, r, p << 1 | 1));
  65.     pushup(p);
  66.     return res;
  67. }
  68.  
  69. char opt[N];
  70.  
  71. void solve() {
  72.     cin >> n;
  73.     set<int> st;
  74.     for (int i = 1; i <= n; i ++) {
  75.         cin >> opt[i] >> seg[i].l >> seg[i].r;
  76.         st.insert(seg[i].l);
  77.         st.insert(seg[i].r);
  78.     }
  79.     cnt = 0;
  80.     for (auto x: st) {
  81.         id[x] = ++ cnt;
  82. //      cout << x << ' ' << cnt << endl;
  83.     }
  84.     build(1, cnt, 1);
  85.     int tot = 0;
  86.     for (int i = 1; i <= n; i ++) {
  87.         if (opt[i] == '+') {
  88.             tot ++;
  89. //          cout << "+ l =" << id[seg[i].l] << " r =" << id[seg[i].r] << endl;
  90.             update(1, cnt, id[seg[i].l], id[seg[i].r], 1, 1);
  91.         } else {
  92.             tot --;
  93. //          cout << "- l : " << id[seg[i].l] << " r : " << id[seg[i].r] << endl;
  94.             update(1, cnt, id[seg[i].l], id[seg[i].r], 1, -1);
  95.         }  
  96.         int res = query(1, cnt, 1, cnt, 1);
  97.         if (res < tot) cout << "YES\n";
  98.         else cout << "NO\n";
  99.     }
  100.     return;
  101. }
  102.  
  103. signed main() {
  104.     ios::sync_with_stdio(false);
  105.     cin.tie(0), cout.tie(0);
  106.     int _ = 1;
  107. //  cin >> _;
  108.     while (_--){
  109.         solve();
  110.     }
  111.     return 0;
  112. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement