Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- #define endl '\n'
- const int N = 1e5 + 10;
- int n, m;
- struct str {
- ll l, r;
- bool operator < (const str & tmp) const {
- return r > tmp.r;
- }
- } seg[N];
- map<ll, int> id;
- int cnt = 0;
- struct Node{
- int mx, add;
- } node[N << 3];
- void pushup (int p) {
- node[p].mx = max (node[p << 1].mx, node[p << 1 | 1].mx);
- }
- void build (int s, int t, int p) {
- node[p].add = 0;
- if (s == t) {
- node[p].mx = 0;
- return;
- }
- int mid = (s + t) >> 1;
- build(s, mid, p << 1);
- build(mid + 1, t, p << 1 | 1);
- pushup(p);
- }
- void pushdown(int p) {
- if (node[p].add) {
- node[p << 1].add += node[p].add;
- node[p << 1].mx += node[p].add;
- node[p << 1 | 1].add += node[p].add;
- node[p << 1 | 1].mx += node[p].add;
- node[p].add = 0;
- }
- }
- void update (int s, int t, int l, int r, int p, int v) {
- if (l <= s && t <= r) {
- node[p].mx += v;
- node[p].add += v;
- return;
- }
- pushdown(p);
- int mid = (s + t) >> 1;
- if (l <= mid) update(s, mid, l, r, p << 1, v);
- if (mid < r) update(mid + 1, t, l, r, p << 1 | 1, v);
- pushup(p);
- }
- int query (int s, int t, int l, int r, int p) {
- if (l <= s && t <= r) return node[p].mx;
- pushdown(p);
- int mid = (s + t) >> 1;
- int res = 0;
- if (l <= mid) res = query(s ,mid, l, r, p << 1);
- if (mid < r) res = max (res, query(mid + 1, t, l, r, p << 1 | 1));
- pushup(p);
- return res;
- }
- char opt[N];
- void solve() {
- cin >> n;
- set<int> st;
- for (int i = 1; i <= n; i ++) {
- cin >> opt[i] >> seg[i].l >> seg[i].r;
- st.insert(seg[i].l);
- st.insert(seg[i].r);
- }
- cnt = 0;
- for (auto x: st) {
- id[x] = ++ cnt;
- // cout << x << ' ' << cnt << endl;
- }
- build(1, cnt, 1);
- int tot = 0;
- for (int i = 1; i <= n; i ++) {
- if (opt[i] == '+') {
- tot ++;
- // cout << "+ l =" << id[seg[i].l] << " r =" << id[seg[i].r] << endl;
- update(1, cnt, id[seg[i].l], id[seg[i].r], 1, 1);
- } else {
- tot --;
- // cout << "- l : " << id[seg[i].l] << " r : " << id[seg[i].r] << endl;
- update(1, cnt, id[seg[i].l], id[seg[i].r], 1, -1);
- }
- int res = query(1, cnt, 1, cnt, 1);
- if (res < tot) cout << "YES\n";
- else cout << "NO\n";
- }
- return;
- }
- signed main() {
- ios::sync_with_stdio(false);
- cin.tie(0), cout.tie(0);
- int _ = 1;
- // cin >> _;
- while (_--){
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement