1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <map> 7 #include <vector> 8 #include <stack> 9 #include <string>10 #include <ctime>11 #include <queue>12 #define mem0(a) memset(a, 0, sizeof(a))13 #define mem(a, b) memset(a, b, sizeof(a))14 #define lson l, m, rt << 115 #define rson m + 1, r, rt << 1 | 116 #define eps 0.000000117 #define lowbit(x) ((x) & -(x))18 #define memc(a, b) memcpy(a, b, sizeof(b))19 #define x_x(a) ((a) * (a))20 #define LL long long21 #define DB double22 #define pi 3.1415926535923 #define MD 1000000724 #define INF (int)1e925 #define max(a, b) ((a) > (b)? (a) : (b))26 using namespace std;27 int b[110000];28 LL solve(int a[], int n, int x)29 {30         LL ans = 0;31         for(int i = 1; i <= n; i++) {32                 int tmp = upper_bound(a + 1, a + 1 + n, x - a[i]) - a;33                 ans += n - tmp + 1;34         }35         return ans;36 }37 int main()38 {39         //freopen("input.txt", "r", stdin);40         //freopen("output.txt", "w", stdout);41         int n, k, T;42         cin>> T;43         while(T--) {44                 cin>> n>> k;45                 LL ans1 = 0, ans2 = 0;46                 int tot = 0;47                 for(int i = 1; i <= n; i++) {48                         int m, a[110];49                         cin>> m;50                         for(int j = 1; j <= m; j++) {51                                 scanf("%d", &a[j]);52                                 b[++tot] = a[j];53                         }54                         sort(a + 1, a + 1 + m);55                         ans1 += solve(a, m, k);56                 }57                 sort(b + 1, b + 1 + tot);58                 ans2 = solve(b, tot, k);59                 cout<< (ans2 - ans1) / 2<< endl;60         }61         return 0;62 }

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cmath>  5 #include <algorithm>  6 #include <map>  7 #include <vector>  8 #include <stack>  9 #include <string> 10 #include <ctime> 11 #include <queue> 12 #define mem0(a) memset(a, 0, sizeof(a)) 13 #define mem(a, b) memset(a, b, sizeof(a)) 14 #define lson l, m, rt << 1 15 #define rson m + 1, r, rt << 1 | 1 16 #define eps 0.0000001 17 #define lowbit(x) ((x) & -(x)) 18 #define memc(a, b) memcpy(a, b, sizeof(b)) 19 #define x_x(a) ((a) * (a)) 20 #define LL long long 21 #define DB double 22 #define pi 3.14159265359 23 #define MD 10000007 24 #define INF (int)1e9 25 #define max(a, b) ((a) > (b)? (a) : (b)) 26 using namespace std; 27 map<int, int> hash; 28 int nn, tot, arr[220000], arr0[220000], c[220000], a[1200][120], m[1200]; 29 void init() 30 { 31         sort(arr + 1, arr + 1 + tot); 32         arr0[1] = arr[1]; 33         nn = 1; 34         hash[arr0[1]] = 1; 35         for(int i = 2; i <= tot; i++) { 36                 if(arr[i] != arr[i - 1]) { 37                         arr0[++nn] = arr[i]; 38                         hash[arr[i]] = nn; 39                 } 40         } 41 } 42 void update(int p, int x) 43 { 44         while(p <= nn) { 45                 c[p] += x; 46                 p += lowbit(p); 47         } 48 } 49 void insert(int a[], int n) 50 { 51         for(int i = 1; i <= n; i++) { 52                 int tmp = hash[a[i]]; 53                 update(tmp, 1); 54         } 55 } 56 int sum(int p) 57 { 58         int ans = 0; 59         while(p) { 60                 ans += c[p]; 61                 p -= lowbit(p); 62         } 63         return ans; 64 } 65 int query(int L, int R) 66 { 67         return sum(R) - sum(L - 1); 68 } 69 int find(int x) 70 { 71         int l = 1, r = nn; 72         while(l < r) { 73                 int m = (l + r) >> 1; 74                 if(arr0[m] > x) r = m; 75                 else l = m + 1; 76         } 77         return l; 78 } 79 int main() 80 { 81         //freopen("input.txt", "r", stdin); 82         //freopen("output.txt", "w", stdout); 83         int T; 84         cin>> T; 85         while(T--) { 86                 hash.clear(); 87                 mem0(c); 88                 int n, k; 89                 cin>> n>> k; 90                 tot = 0; 91                 for(int i = 1; i <= n; i++) { 92                         cin>> m[i]; 93                         for(int j = 1; j <= m[i]; j++) { 94                                 scanf("%d", &a[i][j]); 95                                 arr[++tot] = a[i][j]; 96                         } 97                 } 98                 init(); 99                 insert(a[1], m[1]);100                 LL ans = 0;101                 for(int i = 2; i <= n; i++) {102                         for(int j = 1; j <= m[i]; j++) {103                                 int tmp = find(k - a[i][j]);104                                 ans += query(tmp, nn);105                         }106                         insert(a[i], m[i]);107                 }108                 cout<< ans<< endl;109         }110         return 0;111 }