Advertisement
aayyk

Untitled

Nov 6th, 2019
171
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9. #include <string>
  10. #include <set>
  11. #include <cmath>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <numeric>
  15. #include <random>
  16. #include <memory>
  17. #include <chrono>
  18. #include <iterator>
  19. #include <functional>
  20. #include <unordered_set>
  21. #include <cassert>
  22. #ifdef LOCAL
  23. #include "debug.h"
  24. #else
  25. #define debug(x...)
  26. #endif
  27. //#pragma GCC optimize("Ofast")
  28. //#define int ll
  29.  
  30.  
  31.  
  32. using namespace std;
  33. typedef long long ll;
  34. typedef long double ld;
  35. typedef pair <int, int> pii;
  36. #define mp make_pair
  37. #define pb push_back
  38. #define sz(x) int((x).size())
  39.  
  40. #ifndef LOCAL
  41. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  42. #else
  43. mt19937 rng(228);
  44. #endif
  45.  
  46. const int N = 2e3 + 7;
  47. const int inf = INT_MAX / 2;
  48. const ll INF = LLONG_MAX / 3;
  49. const int MOD = 1e9 + 7;
  50. const double eps = 1e-6;
  51. const string cars[] = {"🚗", "🚕", "🚙"};
  52.  
  53. struct sparse {
  54.     private: vector < vector < float > > a;
  55.     private: short log;
  56.  
  57.     private: int flog(int x) {
  58.         return 32 - __builtin_clz(x) - 1;
  59.     }
  60.  
  61.     public: sparse(vector < float >& v) {
  62.         log = ceil(flog(sz(v)));
  63.  
  64.         a = vector < vector < float > > (sz(v), vector < float > (log + 1));
  65.  
  66.         for (int i = 0; i < sz(v); i++) {
  67.             a[i][0] = v[i];
  68.         }
  69.  
  70.  
  71.         for (int j = 1; j <= log; j++) {
  72.             for (int i = sz(v) - 1; i >= 0; i--) {
  73.                 if (i + (1 << (j - 1)) < sz(a)) {
  74.                     a[i][j] = min(a[i + (1 << (j - 1))][j - 1], a[i][j - 1]);
  75.                 }
  76.             }
  77.         }
  78.     }
  79.     public: sparse() {}
  80.  
  81.     public: float query(int l, int r) {
  82.         int j = flog(r - l + 1);
  83.  
  84.         return min(a[l][j], a[r - (1 << j) + 1][j]);
  85.     }
  86. };
  87.  
  88. int a[N], b[N];
  89. float f[N][N];
  90. sparse F[2 * N];
  91.  
  92. float check(int k, int w, short n, short m) {
  93.     float ans = INF;
  94.  
  95.     for (short i = 0; i < n; i++) {
  96.         for (short j = 0; j < m; j++) {
  97.             short xy = k + i + j - 2;
  98.  
  99.             short xs = min(max(i, short(xy - m + 1)), short(n - 1));
  100.             short xf = min(n - 1, xy - j);
  101.  
  102.  
  103.             if (xs > xf || xy > n + m - 2) {
  104.                 continue;
  105.             }
  106.  
  107.             ans = min(ans, F[xy].query(xs, xf) + 2 * float(sqrt(1LL * (a[i] - b[j]) * (a[i] - b[j]) + w * w)) - f[i][j]);
  108.         }
  109.     }
  110.     return ans;
  111. }
  112.  
  113.  
  114. signed main() {
  115. #ifdef LOCAL
  116.     freopen("input.txt", "r", stdin);
  117.     freopen("output.txt", "w", stdout);
  118. #endif
  119.     cout << fixed << setprecision(9);
  120.     ios::sync_with_stdio(false);
  121.     cin.tie();
  122.     cout.tie();
  123.  
  124.     int l, w, n, m;
  125.     cin >> l >> w >> n;
  126.  
  127.     for (int i = 0; i < n; i++) {
  128.         cin >> a[i];
  129.     }
  130.  
  131.     cin >> m;
  132.  
  133.     for (int i = 0; i < m; i++) {
  134.         cin >> b[i];
  135.     }
  136.  
  137.     for (int i = 0; i < n; i++) {
  138.         for (int j = 0; j < m; j++) {
  139.             f[i][j] = a[i] + b[j] + w + sqrt(1LL * (b[j] - a[i]) * (b[j] - a[i]) + w * w);
  140.         }
  141.     }
  142.    
  143.     for (int j = 0; j < m; j++) {
  144.         int x = 0, y = j;
  145.  
  146.         vector < float > t;
  147.  
  148.         for (; x < n && y >= 0; x++, y--) {
  149.             t.push_back(f[x][y]);
  150.         }
  151.  
  152.         F[j] = sparse(t);
  153.     }
  154.  
  155.     for (int j = m; j < n + m - 1; j++) {
  156.         int x = j - m + 1, y = m - 1;
  157.  
  158.         vector < float > t;
  159.  
  160.         for (; x < n && y >= 0; x++, y--) {
  161.             t.push_back(f[x][y]);
  162.         }
  163.  
  164.         reverse(t.begin(), t.end());
  165.  
  166.         while (sz(t) < x) {
  167.             t.push_back(INF);
  168.         }
  169.  
  170.         reverse(t.begin(), t.end());
  171.  
  172.         F[j] = sparse(t);
  173.     }
  174.  
  175.  
  176.     if (check(2, w, n, m) > l) {
  177.         return cout << 0, 0;
  178.     }
  179.  
  180.     int left = 2, right = n + m + 1;
  181.     while (right - left > 1) {
  182.         int mid = (left + right) / 2;
  183.  
  184.         if (check(mid, w, n, m) < l) {
  185.             left = mid;
  186.         }
  187.         else {
  188.             right = mid;
  189.         }
  190.     }
  191.  
  192.     cout << (check(right, w, n, m) > l ? left : right);
  193.    
  194.     return 0;
  195. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement