fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll=long long int;
  5. using ld=long double;
  6.  
  7. const ll mod=1000000007;
  8. const ll te9=1000000000;
  9. const ll te5=100001;
  10.  
  11. #define prec(a) fixed<<setprecision(a)
  12. #define prhi cout<<"hi"<<endl
  13. #define prcon(a) cout<<a<<endl
  14. #define tdv(n,m,l,a) vector<vector<l>> a(n,vector<l> (m,0))
  15. #define vec(m,a) vector<m> a
  16. #define loop(i,s,e,c) for(ll i=s;i<=e;i+=c)
  17. #define rloop(i,s,e,c) for(ll i=s;i>=e;i-=c)
  18.  
  19. // list of functions
  20. double logb(double n,double b); // for log of any base
  21. void yn(bool); // for printing yes and no
  22. void ab(bool);  // for printing alice and bob
  23. void binary(ll,vector<int> &);   // for converting number into binary
  24. ll lcs(string,string,ll,ll);     // longest common subsequence
  25. void LongestSubarraySum(vector<ll> &v,vector<ll> &ve); // Kadane Algorithm
  26. ll modInverse(ll a, ll m); // for calculating mod Inverse
  27. void fact(ll n,ll m); // for calculating Factorial of number
  28. ll NCR(ll n,ll r,ll m); // for calculating nCr
  29. int xor_1ton(ll n); // find the xor of first n natural number {1^2^3^.....^n}
  30. void solve(); // solution of the problem
  31.  
  32. template <typename dt>
  33. void iar(ll n,vector<dt> &v)
  34. {
  35.     dt k;
  36.     for(ll i=0; i<n; i++)
  37.     {
  38.         cin>>k;
  39.         v.push_back(k);
  40.     }
  41. }
  42. template <typename dt1,typename dt2>
  43. void carip(ll n,vector<dt1> &v1,vector<dt2> &v2,vector<pair<dt1,dt2>> &v3)
  44. {
  45.     for(ll i=0; i<n; i++)
  46.     {
  47.         v3.push_back({v1[i],v2[i]});
  48.     }
  49. }
  50. template <typename dt>
  51. void iarm(ll n,ll m,vector<vector<dt>> &v)
  52. {
  53.     dt k;
  54.     for(ll i=0; i<n; i++)
  55.     {
  56.         for(ll j=0; j<m; j++)
  57.         {
  58.             cin>>k;
  59.             v[i][j]=k;
  60.         }
  61.     }
  62. }
  63. template <typename dt>
  64. void sortv(vector<dt> &v,bool c=true)
  65. {
  66.     if(c)
  67.         sort(v.begin(),v.end());
  68.     else
  69.         sort(v.begin(),v.end(),greater<dt>());
  70. }
  71. template <typename dt>
  72. void print(vector<dt> &v)
  73. {
  74.     for(auto i:v)
  75.         cout<<i<<" ";
  76.     cout<<endl;
  77. }
  78. double logb(double n,double b=2)
  79. {
  80.     return (log(n)/(log(b)*1.0));
  81. }
  82. void yn(bool f=true)
  83. {
  84.     if(f)
  85.         cout<<"YES";
  86.     else
  87.         cout<<"NO";
  88.     cout<<endl;
  89. }
  90. void ab(bool f=true)
  91. {
  92.     if(f)
  93.         cout<<"Alice";
  94.     else
  95.         cout<<"Bob";
  96.     cout<<endl;
  97. }
  98. void binary(ll n,vector<int> &v)
  99. {
  100.     while(n!=0)
  101.     {
  102.         v.push_back(n%2);
  103.         n/=2;
  104.     }
  105.     return ;
  106. }
  107. ll lcs(string X, string Y, ll m, ll n)
  108. {
  109.     ll L[m + 1][n + 1];
  110.     for (ll i = 0; i <= m; i++) {
  111.         for (ll j = 0; j <= n; j++) {
  112.             if (i == 0 || j == 0)
  113.                 L[i][j] = 0;
  114.  
  115.             else if (X[i - 1] == Y[j - 1])
  116.                 L[i][j] = L[i - 1][j - 1] + 1;
  117.  
  118.             else
  119.                 L[i][j] = max(L[i - 1][j], L[i][j - 1]);
  120.         }
  121.     }
  122.     return L[m][n];
  123. }
  124. void LongestSubarraySum(vector<ll> &v,vector<ll> &ve)
  125. {
  126.     ll e=0,c=v[0],g=v[0],s;
  127.     for(ll i=1; i<v.size(); i++)
  128.     {
  129.         c=max(v[i],c+v[i]);
  130.         if(c>g)
  131.         {
  132.             g=c;
  133.             e=i;
  134.         }
  135.     }
  136.     s=e;
  137.     while(s>=0)
  138.     {
  139.         g-=v[s];
  140.         if(g==0)
  141.             break;
  142.         s--;
  143.     }
  144.     for(ll i=s; i<=e; i++)
  145.         ve.push_back(v[i]);
  146.     print(ve);
  147. }
  148. vector<ll> factorial(te5,-1);
  149. vector<ll> Invfactorial(te5,-1);
  150. ll modInverse(ll a, ll m=mod) 
  151. {
  152.     ll res = 1, exp = m - 2;
  153.     while (exp > 0) 
  154.     {
  155.         if (exp % 2 == 1) 
  156.         {
  157.             res = (res * a) % m;
  158.         }
  159.         a = (a * a) % m;
  160.         exp /= 2;
  161.     }
  162.     return res;
  163. }
  164. void fact(ll n,ll m=mod)
  165. {
  166.     factorial[0]=1;
  167.     for(ll i=1;i<=n;i++)
  168.     {
  169.         factorial[i]=(factorial[i-1]*i)%m;
  170.     }
  171.     Invfactorial[n]=modInverse(factorial[n],m);
  172.     for(ll i=n-1;i>=0;i--)
  173.     {
  174.         Invfactorial[i]=(Invfactorial[i+1]*(i+1))%m;
  175.     }
  176. }
  177. ll NCR(ll n,ll r,ll m=mod)
  178. {
  179.     if(n<r || r<0)
  180.     return 0;
  181.     ll k=((factorial[n]*Invfactorial[r])%m);
  182.     return (Invfactorial[n-r]*k)%m;
  183. }
  184. ll binarySearch(ll i,ll j,ll key,vector<ll> &v)
  185. {
  186.     if(i<=j)
  187.     {
  188.         ll m=j+(i-j)/2;
  189.         if(v[m]==key) return m+1;
  190.         else
  191.         {
  192.             if(v[m]>key) return binarySearch(i,m-1,key,v);
  193.             else return binarySearch(m+1,j,key,v);
  194.         }
  195.     }
  196.     return 0;
  197. }
  198. int xor_1ton(ll n)
  199. {
  200.     if(n%4==0) return n;
  201.     else if(n%4==1) return 1;
  202.     else if(n%4==2) return n+1;
  203.     else return 0;
  204. }
  205. int main()
  206. {
  207.     ll t;
  208.     cin>>t;
  209.     // t=1;
  210.     while(t>0)
  211.     {
  212.         // cout<<t<<" ";
  213.         solve();
  214.         t--;
  215.     }
  216.     return 0;
  217. } 
  218.  
  219. void solve()
  220. {
  221.     ll n,m;
  222.     ll ans=0;
  223.     cin>>n>>m;
  224.     vector<ll> a;
  225.     vector<ll> r;
  226.     iar(n,a);
  227.     iar(n,r);
  228.     map<ll,ll> mp;
  229.     for(ll i=0;i<n;i++)
  230.     {
  231.         ll xst=a[i]-r[i];
  232.         ll xen=a[i]+r[i];
  233.         for(ll k=xst;k<=xen;k++)
  234.         {
  235.             ll eq=sqrt((r[i]*r[i])-((k-a[i])*(k-a[i])));
  236.             mp[k]=max(mp[k],eq+1);
  237.         }
  238.     }
  239.     for(auto i:mp) ans+=(2*i.second)-1;
  240.     cout<<ans<<endl;
  241.  
  242. }
Success #stdin #stdout 0.19s 29832KB
comments (?)
stdin
copy 
1
1 200000
-1000000000
200000
stdout
copy 
125663704421
https://ideone.com/x4JRKD
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!