Niuke monthly race - logarithmic sum in groups

Original link

Title Description

The children in Niuniu kindergarten are playing games .
Kindergarten co ownership n Two children , The first i Children have $s_i$ A digital , The first i The number in the hands of a child jj The number is recorded as $a_{ij}(1\le j\le s_i)$.
Now teacher Niuniu wants to know how many different ways to take a number from two different children to make the sum of the numbers greater than or equal k ？
Because there may be many possible ways , So you just need to tell Niuniu about the numerical simulation of this scheme 998244353 Then the result will be ok （ The answers made up of the same number in the hands of the same child are regarded as different ）.

sample input

3 7
4 2 3 1 5
2 4 1
2 8 2

sample output

9

---

Algorithm

( The principle of tolerance and exclusion + Two points search )

The first thing that comes to mind in this topic is pop search enumeration , Enumerate and search all the sum greater than k The possibility of , But it will obviously time out , It's a square level of complexity

therefore , We can think of , This topic k Already given , So we only ask for each number and k How many numbers are there that have a greater difference between , Then it's not difficult to think of sorting first and then using binary search .

Because each number search cannot contain this group of numbers , We can find two intervals each time , Subtract the number of cells from the number of large interval searches , Finally, accumulation is the answer .

C++ Code

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;const ll mod = 998244353;
    
int main()
{
    ll n,k,cnt;
    cin >> n >> k;
    vector<ll> v[N],all; 
    for (int i = 0;i < n;i ++ ) {
        int m;
        cin >> m;
        for (int j = 0;j < m;j ++ ) {
            int x;
            cin >> x;
            v[i].push_back(x);
            all.push_back(x);
            cnt ++;
        }
        sort(v[i].begin() , v[i].end());
    }
    sort(all.begin(),all.end());
    
    ll res = 0,t1 = 0,t2 = 0;
    for (int i = 0;i < n;i ++ ) {
        for (int j = 0;j < v[i].size();j ++ ) {
            t1 = 0,t2 = 0;
            t1 = lower_bound(v[i].begin(),v[i].end(),k - v[i][j]) - v[i].begin();
            t1 = (ll)v[i].size() - t1;
            t2 = lower_bound(all.begin(),all.end(),k - v[i][j]) - all.begin();
            t2 = cnt - t2;
            //cout << t2 << ' ' << t1 << '\n';
            res = (res + t2 - t1) % mod;
        }
    }
    cout << res / 2 << '\n';
    return 0;
}