Advertisement
cosenza987

Untitled

Jun 5th, 2024
408
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.20 KB | None | 0 0
  1. //Слава Україні, Героям слава
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. const int N = 5e5 + 7, M = (1 << 20) + 1;
  8.  
  9. using vll = __int128_t;
  10.  
  11. long long binexp(long long a, long long n, int mod) {
  12.     long long res = 1;
  13.     while(n) {
  14.         if(n & 1) {
  15.             res = (res * a) % mod;
  16.         }
  17.         n >>= 1;
  18.         a = (a * a) % mod;
  19.     }
  20.     return res;
  21. }
  22.  
  23. namespace ntt {
  24.     long long w[M], k, nrev;
  25.     inline void init(int n, int root, int mod) {
  26.         w[0] = 1;
  27.         k = binexp(root, (mod - 1) / n, mod);
  28.         nrev = binexp(n, mod - 2, mod);
  29.         for(int i = 1; i <= n; i++) {
  30.             w[i] = (w[i - 1] * k) % mod;
  31.         }
  32.     }
  33.     inline void ntt(vector<long long> &a, int n, int mod, bool inv = false) {
  34.         a.resize(n);
  35.         for(int i = 0, j = 0; i < n; i++) {
  36.             if(i > j) swap(a[i], a[j]);
  37.             for(int l = n / 2; (j ^= l) < l; l >>= 1);
  38.         }
  39.         for(int i = 2; i <= n; i <<= 1) {
  40.             for(int j = 0; j < n; j += i) {
  41.                 for(int l = 0; l < i / 2; l++) {
  42.                     int x = j + l, y = j + l + (i / 2), z = (n / i) * l;
  43.                     long long tmp = (a[y] * w[(inv ? (n - z) : z)]) % mod;
  44.                     a[y] = (a[x] - tmp + mod) % mod;
  45.                     a[x] = (a[j + l] + tmp) % mod;
  46.                 }
  47.             }
  48.         }
  49.         if(inv) {
  50.             for(int i = 0; i < n; i++) {
  51.                 a[i] = (a[i] * nrev) % mod;
  52.             }
  53.         }
  54.     }
  55.     vector<long long> multiply(vector<long long>& a, vector<long long>& b, int n, int root = 3, int mod = 998244353) {
  56.         init(n, root, mod);
  57.         ntt(a, n, mod);
  58.         ntt(b, n, mod);
  59.         vector<long long> ans(n);
  60.         for(int i = 0; i < n; i++) {
  61.             ans[i] = (a[i] * b[i]) % mod;
  62.         }
  63.         ntt(ans, n, mod, true);
  64.         return ans;
  65.     }
  66.     vector<vll> multiply_garner(vector<long long> &a, vector<long long> &b, vll mod) {
  67.         vector<long long> primes = {1004535809, 998244353, 985661441};
  68.         vector<long long> x[3], y[3], z[3];
  69.         int n = a.size() + b.size() - 1;
  70.         while(n & (n - 1)) n++;
  71.         a.resize(n);
  72.         b.resize(n);
  73.         for(int p = 0; p < 3; p++) {
  74.             x[p].resize(n);
  75.             y[p].resize(n);
  76.             for(int i = 0; i < n; i++) {
  77.                 x[p][i] = a[i] % primes[p];
  78.                 y[p][i] = b[i] % primes[p];
  79.             }
  80.         }
  81.         for(int p = 0; p < 3; p++) {
  82.             z[p] = multiply(x[p], y[p], n, 3, primes[p]);
  83.         }
  84.         vector<vll> ans(n);
  85.         long long r01 = binexp(primes[0], primes[1] - 2, primes[1]);
  86.         long long r02 = binexp(primes[0], primes[2] - 2, primes[2]);
  87.         long long r12 = binexp(primes[1], primes[2] - 2, primes[2]);
  88.         for(int i = 0; i < n; i++) {
  89.             vll a0 = z[0][i];
  90.             vll a1 = (((z[1][i] - z[0][i] + 2 * primes[1]) % primes[1]) * r01) % primes[1];
  91.             vll a2 = (((z[2][i] - z[0][i] + 2 * primes[2]) % primes[2]) * r02) % primes[2];
  92.             a2 = ((a2 - a1 + 2 * primes[2]) % primes[2]) * r12 % primes[2];
  93.             vll res = a0 % mod;
  94.             res = (res + a1 * (primes[0] % mod)) % mod;
  95.             res = (res + a2 * ((primes[0] % mod) * (primes[1] % mod) % mod)) % mod;
  96.             ans[i] = res;
  97.         }
  98.         return ans;
  99.     }
  100. }
  101.  
  102. int main() {
  103.     ios_base::sync_with_stdio(false);
  104.     cin.tie(nullptr);
  105.     int n, m;
  106.     cin >> n >> m;
  107.     vector<long long> a(N), b(N), _a(N), _b(N);
  108.     while(n--) {
  109.         int x, y;
  110.         cin >> x >> y;
  111.         a[x] = y;
  112.         _a[x] = 1;
  113.     }
  114.     while(m--) {
  115.         int x, y;
  116.         cin >> x >> y;
  117.         b[x] = y;
  118.         _b[x] = 1;
  119.     }
  120.     long long same = 0;
  121.     for(int i = 0; i < N; i++) {
  122.         if(_a[i] and _b[i]) {
  123.             same += a[i] + b[i];
  124.             a[i] = b[i] = 0;
  125.         }
  126.     }
  127.     auto l = ntt::multiply_garner(a, _b, (1ll << 61) - 1);
  128.     auto r = ntt::multiply_garner(b, _a, (1ll << 61) - 1);
  129.     long long mx = 0;
  130.     for(int i = 0; i < (int)min(l.size(), r.size()); i += 2) {
  131.         mx = max(mx, (long long)(l[i] + r[i]));
  132.     }
  133.     cout << same + mx << "\n";
  134.     return 0;
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement