牛客小白月赛52--E 分组求对数和(二分)

E 分组求对数和

题目思路

思路：从所有的数中找出两个大于k的数字的方案数减去从一个人那里找出的两个数大于k的方案即为答案

题目代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N=1e6+10;
const ll INF=2000000000;
const int mod=998244353;
int n,k;
vector<int> g[N],h;
int cal(vector<int>&s){
    
    sort(s.begin(),s.end());
    int ans=0;
    for(int i=0;i<s.size();i++){
    
       int res=lower_bound(s.begin()+i+1,s.end(),k-s[i])-s.begin();
       res=s.size()-res+1;
       ans+=res;
       ans%=mod;
    }
    return ans;
}
int main(){
    
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    
        int s;
        cin>>s;
        for(int j=1;j<=s;j++){
    
            int x;
            cin>>x;
            g[i].push_back(x);
            h.push_back(x);
        }
    }
    int ans=0;
    ans=cal(h);
    for(int i=1;i<=n;i++){
    
        ans=(ans-cal(g[i])+mod)%mod;
    }
    cout<<ans;
    return 0;
}