Submission #1519172

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

struct starry_sky_tree {
    int size;
    vector<int> data;
    vector<int> lazy;
    vector<int> width;

    starry_sky_tree(int n) {
        size = 1;
        while (size < n) size <<= 1;
        data.resize(size*2, 0);
        lazy.resize(size*2, 0);
        width.resize(size*2, 1);
        for (int i = size-2; i >= 0; i--) {
            width[i] = width[i*2+1] ; width[i*2+2];
        }
    }

    void lazy_propagate(int p) {
        data[p] += lazy[p];
        if (p < size-1) {
            lazy[p*2+1] += lazy[p];
            lazy[p*2+2] += lazy[p];
        }
        lazy[p] = 0;
    }

    void add(int wishl, int wishr, int x) {
        add(wishl, wishr, 0, size, 0, x);
    }
    void add(int wishl, int wishr, int watchl, int watchr, int k, int x) {
        if (wishr <= watchl || watchr <= wishl) {
            lazy_propagate(k);
            return;
        }
        if (wishl <= watchl && watchr <= wishr) {
            lazy[k] += x;
            lazy_propagate(k);
            return;
        }

        int mid = (watchl + watchr) / 2;
        lazy_propagate(k);
        add(wishl, wishr, watchl, mid, k*2+1, x);
        add(wishl, wishr, mid, watchr, k*2+2, x);
        data[k] = max(data[k*2+1], data[k*2+2]);
    }

    int getmax(int wishl, int wishr) {
        return getmax(wishl, wishr, 0, size, 0);
    }
    int getmax(int wishl, int wishr, int watchl, int watchr, int k) {
        if (wishr <= watchl || watchr <= wishl) return 0;
        if (wishl <= watchl && watchr <= wishr) {
            lazy_propagate(k);
            return data[k];
        }

        int mid = (watchl + watchr) / 2;
        int L = getmax(wishl, wishr, watchl, mid, k*2+1);
        int R = getmax(wishl, wishr, mid, watchr, k*2+2);
        return max(L, R);
    }
};

int main() {
    starry_sky_tree sst(100005);
    int n;
    cin >> n;
    vector<int> s(n), t(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i] >> t[i];
        sst.add(s[i], t[i], 1);
    }

    int ans = sst.getmax(0, 100005);
    for (int i = 0; i < n; i++) {
        sst.add(s[i], t[i], -1);
        int tmp = sst.getmax(0, 100005);
        if (ans > tmp) {
            ans = tmp;
        }
        sst.add(s[i], t[i], 1);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Judge Result