codeforces（D. Rescue Nibel!）（排序，二分）

原题链接

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#include 
#define pb push_back
#define ll long long
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
inline int read() {char c = getchar(); int x = 0, f = 1;while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x * f;
}
using namespace std;ll n,k,ans;
ll mod=998244353;
struct node
{ll x,y;
}e[300005];
ll c[300005],a[300005];
bool cmp(node a,node b)
{if(a.x<b.x){return 1;}return 0;
}
ll apow(ll a,ll b)
{ll s=1;while(b){if(b&1){s=s*a%mod;}a=a*a%mod;b>>=1;}return s;
}
void init()
{c[k-1]=1;ll val=1,base=1;for(ll i=1;i<=k-1;i++){val=val*i%mod;}for(ll i=1;i<=k-1;i++){base=base*apow(i,mod-2)%mod;}for(ll i=k;i<=n;i++){val=val*i%mod;val=val*apow(i-(k-1),mod-2)%mod;c[i]=val*base%mod;}
}
ll query(ll key)
{ll pos=lower_bound(a+1,a+1+n,key)-a;return n-pos+1;
}
int main()
{scanf("%lld %lld",&n,&k);for(int i=1;i<=n;i++){scanf("%lld %lld",&e[i].x,&e[i].y);}init();sort(e+1,e+1+n,cmp);for(int i=1;i<=n;i++){a[i]=e[i].y;}sort(a+1,a+1+n);for(int i=n;i>=1;i--){ll cc=query(e[i].x);cc-=(n-i+1);if(cc>=(k-1)){ans=(ans+c[cc])%mod;}}printf("%lld\n",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！