cosenza987

Untitled

Jun 5th, 2024
614
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.77 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<long long> multiply_crt2(vector<long long> &a, vector<long long> &b, long long mod) {
  67.         vector<long long> primes = {1004535809, 998244353, 985661441};
  68.         vector<long long> x[2], y[2], z[2];
  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 < 2; 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 < 2; p++) {
  82.             z[p] = multiply(x[p], y[p], n, 3, primes[p]);
  83.         }
  84.         vector<long long> ans(n);
  85.         long long r01 = binexp(primes[0], primes[1] - 2, primes[1]);
  86.         for(int i = 0; i < n; i++) {
  87.             vll l = z[0][i], r = z[1][i];
  88.             vll cur = ((r + primes[1] - l % primes[1]) % primes[1]) * r01 % primes[1];
  89.             ans[i] = (l + (cur * primes[0]) % mod + mod) % mod;
  90.         }
  91.         return ans;
  92.     }
  93. }
  94.  
  95. int main() {
  96.     ios_base::sync_with_stdio(false);
  97.     cin.tie(nullptr);
  98.     int n, m;
  99.     cin >> n >> m;
  100.     vector<long long> a(N), b(N), _a(N), _b(N);
  101.     while(n--) {
  102.         int x, y;
  103.         cin >> x >> y;
  104.         a[x] = y;
  105.         _a[x] = 1;
  106.     }
  107.     while(m--) {
  108.         int x, y;
  109.         cin >> x >> y;
  110.         b[x] = y;
  111.         _b[x] = 1;
  112.     }
  113.     long long same = 0;
  114.     for(int i = 0; i < N; i++) {
  115.         if(_a[i] and _b[i]) {
  116.             same += a[i] + b[i];
  117.             a[i] = b[i] = 0;
  118.         }
  119.     }
  120.     auto l = ntt::multiply_crt2(a, _b, (1ll << 61) - 1);
  121.     auto r = ntt::multiply_crt2(b, _a, (1ll << 61) - 1);
  122.     long long mx = 0;
  123.     for(int i = 0; i < (int)min(l.size(), r.size()); i += 2) {
  124.         mx = max(mx, (l[i] + r[i]));
  125.     }
  126.     cout << same + mx << "\n";
  127.     return 0;
  128. }
Advertisement
Add Comment
Please, Sign In to add comment