Submission #11599935

---

Source Code Expand

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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = (int)2e5 + 50;

#define lson(x) 2*x+1
#define rson(x) 2*x+2

struct node {
    int sum, pref;

    void add(int val) {
        sum += val;
        pref = max(sum, 0);
    }
};

node merge(node L, node R) {
    return {L.sum + R.sum, max(L.sum + R.pref, L.pref)};
}

struct Tree {
    node dat[4 * N];
    void init(int x, int l, int r) {
        if(l == r) {dat[x] = {-1, 0}; return ;}
        int mid = (l + r) / 2;
        init(lson(x), l, mid);
        init(rson(x), mid + 1, r);
        dat[x] = merge(dat[lson(x)], dat[rson(x)]);
    }

    void update(int pos, int x, int l, int r, int val) {
        if(l == r) {dat[x].add(val); return ;}
        int mid = (l + r) / 2;
        if(pos <= mid) update(pos, lson(x), l, mid, val);
        else update(pos, rson(x), mid + 1, r, val);
        dat[x] = merge(dat[lson(x)], dat[rson(x)]);
    }

    node query(int a, int b, int x, int l, int r) {
        if(r < a || b < l) return {0, 0};
        int mid = (l + r) / 2;
        if(a <= l && r <= b) return dat[x];
        else return merge(query(a, b, lson(x), l, mid),
                query(a, b, rson(x), mid + 1, r));
    }
} tree;

int n, m;
vector<int> add[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    int mx = max(0, n - m);
    tree.init(0, 0, m - 1);
    for(int i = 0; i < n; i++) {
        int l, r; cin >> l >> r; l--, r--;
        add[r].push_back(l);
    }
    int cur_r = 0;
    int non = 0;
    for(int r = m; r >= 0; r--) {
        for(auto l : add[r]) {
            if(l >= 0) tree.update(l, 0, 0, m - 1, 1);
            else non++;
        }
        mx = max(mx, tree.dat[0].pref + non - (m - r));
    }
    cout << mx << '\n';
}

Submission Info

Judge Result