Submission #71874529

---

Source Code Expand

// Best papa ikam template — Absolute Performance Limit
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std; using namespace __gnu_pbds;

// --- Types ---
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int,int>; using pll = pair<ll,ll>; using vi = vector<int>; using vll = vector<ll>;
template<class T> using min_heap = priority_queue<T, vector<T>, greater<T>>;

// --- Constants ---
const int MOD = 998244353; 
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;
const ld PI = acos(-1.0L);
const ld EPS = 1e-9;

// --- Macros ---
#define nn '\n'
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define each(x,a) for(auto& x:a)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back

// --- RNG & Hash (SplitMix64 + Golden Ratio) ---
static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() ^ (ull)unique_ptr<char>(new char).get());
struct chash {
    static ull sm64(ull x) { 
        x += 0x9e3779b97f4a7c15; 
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; 
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb; 
        return x ^ (x >> 31); 
    }
    size_t operator()(ull x) const { 
        static const ull R = rng(); return (size_t)sm64(x + R); 
    }
    template<class A, class B> size_t operator()(const pair<A, B>& p) const { 
        static const ull R = rng(); 
        return (size_t)(sm64((ull)p.fi + R) ^ (sm64((ull)p.se + R) >> 1)); 
    }
};

// --- PBDS ---
template<class K, class V> using hash_map = gp_hash_table<K, V, chash>;
template<class K> using hash_set = gp_hash_table<K, null_type, chash>;
template<class T> using ord_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// --- Math & Modular ---
template<int M> struct mint {
    int v; constexpr mint(ll x = 0) : v((int)(x % M < 0 ? x % M + M : x % M)) {}
    mint& operator+=(mint o) { v += o.v; if (v >= M) v -= M; return *this; }
    mint& operator-=(mint o) { v -= o.v; if (v < 0) v += M; return *this; }
    mint& operator*=(mint o) { v = (int)((ll)v * o.v % M); return *this; }
    mint pow(ll e) const { mint r = 1, a = *this; for (; e; e >>= 1, a *= a) if (e & 1) r *= a; return r; }
    mint inv() const { return pow(M - 2); }
    mint operator-() const { return v ? M - v : 0; }
    mint& operator/=(mint o) { return *this *= o.inv(); }
    friend mint operator+(mint a, mint b) { return a += b; }
    friend mint operator-(mint a, mint b) { return a -= b; }
    friend mint operator*(mint a, mint b) { return a *= b; }
    friend mint operator/(mint a, mint b) { return a /= b; }
    friend bool operator==(mint a, mint b) { return a.v == b.v; }
    friend bool operator!=(mint a, mint b) { return a.v != b.v; }
    friend istream& operator>>(istream& i, mint& x) { ll t; i >> t; x = t; return i; }
    friend ostream& operator<<(ostream& o, mint x) { return o << x.v; }
};
using mint_t = mint<MOD>;

struct Combs {
    vector<mint_t> f, i; 
    Combs(int n) : f(n + 1), i(n + 1) { 
        f[0] = 1; rep(j, 1, n + 1) f[j] = f[j - 1] * j;
        i[n] = f[n].inv(); for (int j = n - 1; j >= 0; --j) i[j] = i[j + 1] * (j + 1); 
    }
    mint_t nCr(int n, int r) { return (r < 0 || r > n) ? 0 : f[n] * i[r] * i[n - r]; }
};

// --- Bit & Math Utils ---
inline ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return a; }
inline ll binpow(ll a, ll e) { 
    ll r = 1; for (; e; e >>= 1, a = a * a) if (e & 1) r = r * a; return r; 
}
inline ll mod_pow(ll a, ll e, ll m = MOD) { 
    ll r = 1; a %= m; for (; e; e >>= 1, a = (ll)((__int128)a * a % m)) if (e & 1) r = (ll)((__int128)r * a % m); return r; 
}
#define popcnt __builtin_popcountll
inline int msb(ll x) { return x ? 63 - __builtin_clzll((ull)x) : -1; }
inline bool is_pow2(ull x) { return x && !(x & (x - 1)); }

void solve2() {
    int h,w,n;
    cin >> h >> w >> n;
    vector a(h, vi(w));
    for (auto& i: a) {
        for (auto&j: i) cin >> j;
    }
    hash_set<int> b;
    while (n--) {
        int el;
        cin >> el;
        b.insert(el);
    }
    int mx = 0;
    for (int i=0; i<h; ++i) {
        int count = 0;
        for (int j=0; j<w; ++j) {
            if (b.find(a[i][j]) != b.end()) {
                count++;
            }
        }
        mx = max(mx, count);
    }
    cout << mx;
}

void solve3() {
    int n;
    cin >> n;
    vector<ll> data(n);
    ll total = 0;
    for (int i=0; i<n; ++i) {
        int w,p;
        cin >> w >> p;
        data[i] = w+p;
        total+=p;
    }
    sort(data.begin(), data.end());
    ll got = 0, ans = 0;
    for (int i=0; i<n; ++i) {
        if (total >= got + data[i]) {
            got += data[i];
            ans++;
        }
    }
    cout << ans << nn;
}

void solve() {
    int n,m;
    cin >> n >> m;
    vi a(n), b(m);
    for (auto &i: a) cin >> i;
    for (auto &i: b) cin >> i;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    vector<mint_t> pref(m+1);
    for (int i=0; i<m; ++i) {
        pref[i+1] = pref[i] + b[i];
    }
    mint_t ans = 0;
    for (int i=0; i<n; ++i) {
        int idx  = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        if (idx > 0) {
            ans += mint_t(a[i])*idx - pref[idx];
        }
        if (idx < m) {
            ans += pref[m] - pref[idx] - mint_t(a[i])*(m - idx);
        }
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int T = 1; 
    //cin >> T;
    while (T--) solve();
    return 0;
}

Submission Info

Judge Result