牛客小白月賽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;
}