C++(g++ 7.5.0) 解法, 执行用时: 466ms, 内存消耗: 59016K, 提交时间: 2022-08-10 09:49:39

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
const int mod = 998244353;

vector<int>vec[MAXN], All;

int get(vector<int> &a, int k)
{
    return a.size() - (lower_bound(a.begin(), a.end(), k) - a.begin());
}

int main()
{
	int n, m, k;
	scanf("%d %d", &n, &k);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &m);
		vec[i].resize(m);
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &vec[i][j]);
			All.push_back(vec[i][j]);
		}
		sort(vec[i].begin(), vec[i].end());
	}
	sort(All.begin(), All.end());
	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int x : vec[i])
		{
			ans += get(All, k - x) - get(vec[i], k - x);
		}
	}
	cout << ans / 2 % mod << endl;
}

C++ 解法, 执行用时: 683ms, 内存消耗: 59108K, 提交时间: 2022-07-17 10:49:40

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;

int main(){
	int n, k;
    long long ans = 0;
	vector<int> vec[maxn], all;
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		int t, x;
		cin >> t;
		while(t--){
			cin >> x;
			vec[i].push_back(x);
			all.push_back(x);
		}
        sort(begin(vec[i]), end(vec[i]));
	}
	
    sort(begin(all), end(all));
	for(int i = 0; i < n; i++)
		for(auto& v : vec[i]){
			int t = k - v;
			ans += end(all) - lower_bound(begin(all), end(all), t);
			ans -= end(vec[i]) - lower_bound(begin(vec[i]), end(vec[i]), t);
        }
    cout << ans / 2 % 998244353;
	return 0;
}

Python3 解法, 执行用时: 3740ms, 内存消耗: 136444K, 提交时间: 2022-06-21 09:43:31

import sys
import bisect
input=sys.stdin.readline 
 
def f(a,k):
    #求和>K的数
    
    n=len(a)
    ans=0
    r=n
    l=0
    for i in range(n):
        dj=k-a[i]-1
        index=bisect.bisect_right(a,dj,l,r)
        r=index
        ans+=n-index
        if a[i]>dj:
            ans-=1
    return ans//2               
    
n,k=map(int,input().split())
a=[]
b=[]
for _ in range(n):
    tmp=list(map(int,input().split()))[1:]
    tmp.sort()
    a.append(tmp)
    b+=tmp
b.sort()
ans=f(b,k)
for i in range(len(a)):
    t=f(a[i],k)
    ans-=t
print(ans%998244353)