Submission #11471307

---

Source Code Expand

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
const int INF = (int)1e9;
const int maxN = 2e5 + 10;
int t[4 * maxN];
int lazy[4 * maxN];
void add(int v, int by) {
    t[v] += by;
    lazy[v] += by;
}
void merge(int v) {
    t[v] = max(t[2 * v], t[2 * v + 1]);
}
void push(int v, int tl, int tr) {
    if (tl != tr && lazy[v] != 0) {
        add(2 * v, lazy[v]);
        add(2 * v + 1, lazy[v]);
    }
    lazy[v] = 0;
}
void add(int v, int tl, int tr, int l, int r, int by) {
    if (l <= tl && tr <= r) {
        add(v, by);
        return;
    }
    push(v, tl, tr);
    if (l > tr || r < tl) return;
    int tm = (tl + tr) / 2;
    add(2 * v, tl, tm, l, r, by);
    add(2 * v + 1, tm + 1, tr, l, r, by);
    merge(v);
}
int getMax(int v, int tl, int tr, int l, int r) {
    if (l > r) return -INF;
    if (tl == l && tr == r) {
        return t[v];
    }
    push(v, tl, tr);
    int tm = (tl + tr) / 2;
    return max(getMax(2 * v, tl, tm, l, min(r, tm)), getMax(2 * v + 1, tm + 1, tr, max(tm + 1, l), r));
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = tl;
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

int n, m;
int l[maxN], r[maxN];
vector < int > all[maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("input.txt", "r", stdin);
    cin >> n >> m;
    int mxl = 0;
    int mnr = m + 1;
    for (int i = 1; i <= m; i++) {
        cin >> l[i] >> r[i];
        mxl = max(mxl, l[i]);
        mnr = min(mnr, r[i]);
        all[l[i]].emplace_back(r[i]);
    }
    int mx = max(0, n - m);
//    if (mxl < mnr) {
//        mx = max(mx, n - (m + 1 - mnr + mxl));
//    }
    build(1, 0, m + 1);
    for (int i = 0; i <= m; i++) {
        for (int v : all[i]) {
            add(1, 0, m + 1, 0, v, +1);
        }
        mx = max(mx, -i + getMax(1, 0, m + 1, i + 1, m + 1) - m - 1);
    }
    cout << mx;
    return 0;
}

Submission Info

Judge Result