1420D - Rescue Nibel - CodeForces Solution

#include<bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
using namespace std;
using ll=long long;
const int N=6e5+5;
const double ex = 1e-6;
const ll mod = 998244353 ;
const ll inf = 1e16;
int n, k,  m, lab[N], add[N], del[N], sum;
ll pw(ll k, ll n){
    ll res = 1;
    for(; n; n >>= 1){
        if(n&1)res = res * k % mod;
        k = k *k % mod;
    }
    return res;
}
int findp(int u){
    return lab[u] < 0 ? u : lab[u] = findp(lab[u]);
}
void hop(int u, int v){
    u = findp(u);
    v = findp(v);
    if(u == v)return;
    if(lab[u] > lab[v])swap(u, v);
    lab[u] += lab[v];
    lab[v] = u;
}
struct IT{
    int n;
    vector<ll> st;
    IT(int _n){
        n = _n;
        st.resize(n*4+4);
    }
    void build(int id, int l, int r){
        if(l == r){
            st[id] = l;
            return;
        }
        int mid = (l+r)>>1;
        build(id<<1, l, mid);
        build(id<<1|1, mid+1, r);
        st[id] = max(st[id<<1], st[id<<1|1]);
    }
    void build(){
        build(1, 0, n);
    }
    int get(int id, int l, int r, int u, int v){
        if(u <= l && r <= v){
            return st[id];
        }
        if(u > r || l > v)return 0;
        int mid = (l+r)>>1;
        return (get(id<<1, l, mid, u, v) + get(id<<1|1, mid+1, r, u, v));
    }
    int get(int l, int r){
        return get(1 ,0, n, l, r);
    }
    void update(int id, int l, int r, int pos, int v){
        if(l == r){
            st[id] += v;
            return;
        }
        int mid = (l+r)>>1;
        if(pos <= mid)update(id<<1, l, mid, pos, v);
        else update(id<<1|1, mid+1, r, pos, v);
        st[id] = st[id<<1] + st[id<<1|1];
    }
    void update(int pos, int v){
        update(1, 0, n, pos, v);
    }
};
struct BIT{
    int n;
    vector<int> fe;
    BIT(int _n){
        n = _n;
        fe.resize(n+1, 0);
    }
    void add(int id, int x){
        for(; id <= n; id += id & -id){
            fe[id] += x;
        }
    }
    int get(int id){
        int res = 0;
        for(; id; id -= id & -id)res += fe[id];
        return res;
    }
    void init(int v){
        fill(fe.begin(), fe.end(), v);
    }
};
vector<int> adj[N], vi;
ll a[N], b[N], ans;
int dfs(int u){
    if(a[u] == k)return u;
    a[u] = k;
    if(adj[u].empty())return -1;
    int v = adj[u].back();
    adj[u].pop_back();
    int res = dfs(v);
    adj[u].pb(v);
    return res;

}
pii p[N];
ll C(int u, int v){
    if(u > v)return 0;
    return a[v] * b[u] % mod * b[v-u] % mod;
}
void sol(){
    cin >> n >> k;
    a[0] = b[0] = 1;
    for(int i = 1; i <= n; i ++){
        a[i] = a[i-1] * i % mod;
        b[i] = b[i-1] * pw(i, mod-2) % mod;
    }
    for(int i = 1; i <= n; i ++){
        cin >> p[i].fi >> p[i].se;
        vi.pb(p[i].fi);
        vi.pb(p[i].se);
    }
    sort(vi.begin(), vi.end());
    vi.erase(unique(vi.begin(), vi.end()), vi.end());
    for(int i = 1; i <= n; i ++){
        p[i].fi = lower_bound(vi.begin(), vi.end(), p[i].fi) - vi.begin() + 1;
        p[i].se = lower_bound(vi.begin(), vi.end(), p[i].se) - vi.begin() + 1;
        add[p[i].fi] ++;
        del[p[i].se] --;
    }
    for(int i = 1; i <= (int)vi.size(); i ++){
        sum += add[i];
        ans = (ans + C(k, sum)) % mod;
        sum += del[i];
        add[i] = 0;
        del[i] = 0;
    }
    for(int i = 1; i <= n; i ++){
        if(p[i].fi == p[i].se)continue;
        add[p[i].fi+1] ++;
        del[p[i].se] --;
    }

    sum = 0;
    for(int i = 1; i <= (int)vi.size(); i ++){
        sum += add[i];
        ans = (ans + mod - C(k, sum)) % mod;
        sum += del[i];
        add[i] = 0;
        del[i] = 0;
    }
    cout << ans;
}
int  main(){
    #define task "test"
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t -- > 0){
        sol();
	}
	return 0;
}