fork download
copy 
  1. /*
  2. 	Author: Ritik Patel
  3. */
  4.  
  5.  
  6. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&&
  7.  
  8. // #define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
  9. // #pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
  10.  
  11. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  12.  
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. /*#include <ext/pb_ds/assoc_container.hpp> // Common file
  17. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  18. template<typename T, typename V = __gnu_pbds::null_type>
  19. using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; 
  20. */
  21. //find_by_order()->returns an iterator to the k-th largest element(0-based indexing)
  22. //order_of_key()->Number of items that are strictly smaller than our item
  23.  
  24. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  25.  
  26. #define int long long int
  27. // #define ll long long int
  28. #define all(i) i.begin(), i.end()
  29. #define sz(a) (int)a.size()
  30.  
  31. // #define ld long double
  32. // const ld PI  = 3.141592;
  33. const int dx4[4] = {0, 1, 0, -1};
  34. const int dy4[4] = {-1, 0, 1, 0};
  35. const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  36. const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  37.  
  38. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&&
  39.  
  40. #define XOX
  41. vector<string> vec_splitter(string s) {
  42.     for(char& c: s) c = c == ','?  ' ': c;
  43.     stringstream ss; ss << s;
  44.     vector<string> res;
  45.     for(string z; ss >> z; res.push_back(z));
  46.     return res;
  47. }
  48.  
  49. void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
  50. template <typename Head, typename... Tail>
  51. void debug_out(vector<string> args, int idx, Head H, Tail... T) {
  52.     if(idx > 0) cerr << ", ";
  53.     stringstream ss; ss << H;
  54.     cerr << args[idx] << " = " << ss.str();
  55.     debug_out(args, idx + 1, T...);
  56. }
  57.  
  58. #ifdef XOX
  59. #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
  60. #else
  61. #define debug(...) 42
  62. #endif
  63.  
  64.  
  65. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&&
  66.  
  67. struct data{
  68.     int p, h;
  69.     data() {}
  70.     data(int _p, int _h): p(_p), h(_h) {}
  71. };
  72.  
  73. vector<pair<int, pair<int, pair<int, int>> > > S;
  74. bool vis[800005][2];
  75. set<int> check;
  76.  
  77. int dfs(int i, int id, int which, int L, int R){
  78.  
  79.     vis[id][which] = true;
  80.  
  81.     int lo = i, hi = sz(S) - 1;
  82.     while(lo < hi){
  83.         int mid = (lo + hi) / 2;
  84.         if(S[mid].first >= R){
  85.             hi = mid;
  86.         } else {
  87.             lo = mid + 1;
  88.         }
  89.     }
  90.  
  91.     int ans = R - L; 
  92.     for(int j = lo; j < sz(S); ++j){
  93.         auto p = S[j];
  94.         int start = p.first;
  95.         int end = p.second.first;
  96.         int ii = p.second.second.first;
  97.         int whichii = p.second.second.second;
  98.         if(start != R){
  99.             break;
  100.         }
  101.         if(vis[ii][whichii] or check.count(ii)){
  102.             continue;
  103.         }
  104.         check.insert(ii);
  105.         ans = max(ans, dfs(j, ii, whichii, L, end));
  106.         check.erase(ii);
  107.     }
  108.     return ans;
  109. }
  110.  
  111. void solve(){
  112.  
  113.     int N; cin >> N;
  114.     vector<data> A(N);
  115.  
  116.     //Reset
  117.     S.clear();
  118.     for(int i = 0; i <= N; ++i){
  119.         for(int j = 0; j < 2; ++j){
  120.             vis[i][j] = false;
  121.  
  122.         }
  123.     }
  124.  
  125.  
  126.     for(int i = 0; i < N; ++i){
  127.         int x, y; cin >> x >> y;
  128.         A[i] = {x, y};
  129.         // debug(A[i].p, A[i].h);
  130.     }
  131.  
  132.     for(int i = 0; i < N; ++i){
  133.         S.push_back( { A[i].p - A[i].h, {A[i].p , {i, 0} } } );
  134.         S.push_back( { A[i].p , {A[i].p + A[i].h, {i, 1} } } );
  135.     }
  136.     sort(all(S));
  137.  
  138.     int ans = 0;
  139.     for(int i = 0; i < sz(S); ++i){
  140.  
  141.         auto p = S[i];
  142.         int start = p.first;
  143.         int end = p.second.first;
  144.         int id = p.second.second.first;
  145.         int which = p.second.second.second;
  146.         // debug(i, start, end, id, which);
  147.  
  148.         if(vis[id][which]){
  149.             continue;
  150.         }
  151.         check.clear();
  152.         check.insert(id);
  153.         ans = max(ans, dfs(i, id, which, start, end));
  154.     }
  155.     cout << ans << '\n';
  156.  
  157. }
  158.  
  159. int32_t main(){
  160.     freopen("input.txt","r",stdin);
  161.     freopen("output.txt","w",stdout); 
  162.     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  163.     int T = 1; 
  164.     cin >> T;
  165.     for(int i = 1; i <= T; ++i){
  166.         cout << "Case #" << i << ": ";
  167.         solve();
  168.     }
  169.     return 0;
  170. }
  171.  
  172. /*
  173. Sample inp
  174. */
  175.  
Runtime error #stdin #stdout #stderr 0s 4156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/IICsYZ
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!