Advertisement
Guest User

Untitled

a guest
Mar 9th, 2023
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.87 KB | None | 0 0
  1. //////////////////////////////////////////////////////////////////
  2. ///// //
  3. //// Credits: Rahul Verma (CC @vrintle, CF @BlindingKnight) ///
  4. /// Institution: Delhi Technological University (aka. DCE) ////
  5. // /////
  6. //////////////////////////////////////////////////////////////////
  7.  
  8. #include <chrono>
  9. #include <bits/stdc++.h>
  10. #include <ext/pb_ds/assoc_container.hpp>
  11. using namespace std;
  12. using namespace chrono;
  13. using namespace __gnu_pbds;
  14.  
  15. template <typename T> using pbds = tree<T, null_type,
  16. less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  17. // find_by_order(K): Returns an iterator to the Kth largest element (counting from zero)
  18. // order_of_key (K): Returns the number of items that are strictly smaller than K
  19.  
  20. /*
  21.  
  22. ~ You don't know the power of the dark side! ~
  23.  
  24. ..-..,'".- BM\dF. jM@' !MMM.&^'jjjM#*..`. !*m.F. `.....
  25. -`.'^-".^. ._'-". `` `"#.# .]MF. _. __-gg.. jMg. ......
  26. '......._ j#M' jMf jg_jm..-` .Mf_ ja "` .` `^" ,_ 4g."@!. ...,.,
  27. ',3&^jCgf ._`"`"'. .` """!. .`^^ ..... .""LTgJf. =/<.,
  28. _@#MMQK##-@"^ .. .'QK_. .!$AGz
  29. MM&&#0$#yF. !-M. .gmMM@! ."q. ..K#MD
  30. ZM#ZM#$. q4M. ..__,,yg_. ^\. ..M0#
  31. A0NWM@. jggp. .,m* .#MMMMM#'.. ' ."M0
  32. BMM$@" !MM#'.. -*' ."QMMMM#`.. ..^$
  33. BMMM' .^@#.'` _ ,yy___````. . `
  34. MMMP ... j. 1.L .""9*qwwwJ,. ..
  35. @@@. . ...P`, .F` .`. ..
  36. 0T` .P. . F` :"~~- ._.e.,wyyw..,,....
  37. yg. ' _g0M0g. .-'`'^`Q$_
  38. Mf .jMMMMML .`-"0M#
  39. @. . ."MMMM@^ ."".
  40. f . -. ...
  41. . . ._ ...
  42. . . . ..
  43. .. -' ., .., ..,.
  44. `. . ..*. . _ , .p_ .-,'jb.
  45. _ jgg, -'-+..--!.!!!` !' .~. _0MM/.-.-/@. .yyygggMM
  46. M0gyy__________. ^0M' "MM^ ...". `^MMMMMM
  47. MMMMMMMMMMMMMM'. .. .
  48.  
  49. */
  50.  
  51. #define F first
  52. #define S second
  53. #define db double
  54. #define ld long db
  55. #define M 1000000007
  56. #define pb push_back
  57. #define ll long long
  58. #define lll __int128
  59. #define vl vector<ll>
  60. #define vd vector<db>
  61. #define vld vector<ld>
  62. #define vvl vector<vl>
  63. #define pl pair<ll,ll>
  64. #define pd pair<db,db>
  65. #define vpl vector<pl>
  66. #define vpd vector<pd>
  67. #define lld __float128
  68. #define ull unsigned ll
  69. #define sz(a) ((ll) a.size())
  70. #define PI 3.141592653589793238
  71. #define all(v) v.begin(), v.end()
  72. #define each(seq) for(auto e: seq)
  73. #define inf numeric_limits<ll>::max()
  74. #define acc(a) accumulate(all(a), 0ll)
  75. #define shuff(a) random_shuffle(all(a))
  76. #define F0(n, i) for(ll i = 0; i < n; i++)
  77. #define F1(n, i) for(ll i = 1; i <= n; i++)
  78. #define google cout << "Case #" << i << ": ";
  79. #define dbgpr(pr) cout << ' ' << #pr << " {" << pr.F << ',' << pr.S << "} "
  80. #define dbgprs(seq) cout << #seq << " <"; each(seq) { dbgpr(e); } cout << ">\n"
  81. #define dbgarr(seq) cout << #seq << " < "; each(seq) { cout << e << ' '; } cout << ">\n"
  82. #define dbgmtx(mat) cout << #mat << " {\n"; each(mat) { cout << ' '; dbgarr(e); } cout << "}\n"
  83. #define lrot(a, l, r, k) rotate(a.begin() + l, a.begin() + l + (k % (r - l + 1)), a.begin() + r + 1)
  84. #define rrot(a, l, r, k) rotate(a.begin() + l, a.begin() + r + 1 - (k % (r - l + 1)), a.begin() + r + 1)
  85. #define dbgmap(hash) cout << #hash << " { "; each(hash) { cout << e.first << ':' << e.second << ' '; } cout << "}\n"
  86. #define dbgtree(tree) cout << #tree << " {\n"; each(tree) { cout << e.first << ": "; dbgarr(e.second); } cout << "}\n"
  87.  
  88. // Debug Template, copied from Mikel_Arteta_8 (https://codeforces.com/blog/entry/68809)
  89. void __print(int x) {cerr << x;}
  90. void __print(long x) {cerr << x;}
  91. void __print(long long x) {cerr << x;}
  92. void __print(unsigned x) {cerr << x;}
  93. void __print(unsigned long x) {cerr << x;}
  94. void __print(unsigned long long x) {cerr << x;}
  95. void __print(float x) {cerr << x;}
  96. void __print(double x) {cerr << x;}
  97. void __print(long double x) {cerr << x;}
  98. void __print(char x) {cerr << '\'' << x << '\'';}
  99. void __print(const char *x) {cerr << '\"' << x << '\"';}
  100. void __print(const string &x) {cerr << '\"' << x << '\"';}
  101. void __print(bool x) {cerr << (x ? "true" : "false");}
  102. template<typename T, typename V>
  103. void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
  104. template<typename T>
  105. void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
  106. void _print() {cerr << "]\n";}
  107. template <typename T, typename... V>
  108. void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
  109. #ifdef VRINTLE
  110. #define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
  111. #else
  112. #define debug(x...)
  113. #endif
  114. // End of debugging template
  115.  
  116. /* ostream& operator<<(ostream& o, const __int128& x) {
  117. if (x == numeric_limits<__int128>::min()) return o << "-170141183460469231731687303715884105728";
  118. if (x < 0) return o << "-" << -x;
  119. if (x < 10) return o << (char)(x + '0');
  120. return o << x / 10 << (char)(x % 10 + '0');
  121. } */
  122.  
  123. ll sieve_size = 0, facto_size = 0;
  124. vector<ll> F(facto_size+1);
  125. vector<bool> state(sieve_size+1, 1);
  126. // exp() for (N^K)%M is only valid, when N%M != 0, else return 0
  127. ll exp(ll n,ll k,ll m=M){ll r=1,a=n%m;do{r=k&1?r*a%m:r;a=a*a%m;}while(k/=2);return r;}
  128. ll imod(ll a,ll m=M){return exp(a,m-2,m)%m;}
  129. ll C(ll n,ll r,ll m=M){return r?(F[n]*imod(F[r],m)%m*imod(F[n-r],m)%m)%m:1;}
  130. void facto(ll n=facto_size,ll m=M){F[0]=1;F1(n,i)F[i]=(F[i-1]*i)%m;}
  131. void sieve(ll n=sieve_size){for(ll i=4;i<=n;i+=2)state[i]=0;for(ll i=3;i<=n;i+=2)for(ll j=i*i;j<=n;j+=i)state[j]=0;}
  132. // when floor(-1 / 4) = -1, use this one
  133. template<class T>T fdivf(T a,T b){return a/b-((a^b)<0&&a%b);}
  134.  
  135. const int N = 5e5 + 7;
  136. pl a[N];
  137. map<ll, ll> sta, stb;
  138. map<ll, vl> sa, sb;
  139.  
  140. void solve() {
  141. ll n;
  142. cin >> n;
  143. ll mx = 0;
  144. sta.clear();
  145. stb.clear();
  146. sa.clear();
  147. sb.clear();
  148. vl v;
  149. F0(n, i) {
  150. cin >> a[i].F >> a[i].S;
  151. mx = max(mx, min(a[i].F, a[i].S));
  152. sa[a[i].F].pb(i);
  153. sb[a[i].S].pb(i);
  154. sta[-a[i].F]++;
  155. stb[-a[i].S]++;
  156. v.pb(a[i].F);
  157. v.pb(a[i].S);
  158. }
  159. sort(all(v));
  160. vl _v {v[0]};
  161. for(ll i = 1; i < sz(v); i++) {
  162. if(_v.back() != v[i]) _v.pb(v[i]);
  163. }
  164. swap(_v, v);
  165. ll ans = inf;
  166. for(auto x: v) {
  167. if(x < mx) continue;
  168. if(sa.find(x) != sa.end()) {
  169. for(auto i: sa[x]) {
  170. stb[-a[i].S]--;
  171. if(stb[-a[i].S] == 0) stb.erase(-a[i].S);
  172. auto it = stb.lower_bound(-a[i].F);
  173. if(it == stb.end()) {
  174. stb[-a[i].S]++;
  175. continue;
  176. }
  177. ans = min(ans, x + it->F);
  178. stb[-a[i].S]++;
  179. }
  180. }
  181. if(sb.find(x) != sb.end()) {
  182. for(auto i: sb[x]) {
  183. sta[-a[i].F]--;
  184. if(sta[-a[i].F] == 0) sta.erase(-a[i].F);
  185. auto it = sta.lower_bound(-a[i].S);
  186. if(it == sta.end()) {
  187. sta[-a[i].F]++;
  188. continue;
  189. }
  190. ans = min(ans, x + it->F);
  191. sta[-a[i].F]++;
  192. }
  193. }
  194. }
  195. cout << ans;
  196. }
  197.  
  198. int32_t main() {
  199. auto start = high_resolution_clock::now();
  200. ios_base::sync_with_stdio(false);
  201. cin.tie(NULL);
  202. ll t = 1;
  203. cin >> t;
  204. F1(t, i) {
  205. // google
  206. solve();
  207. cout << '\n';
  208. }
  209. auto stop = high_resolution_clock::now();
  210. auto duration = duration_cast<microseconds>(stop - start);
  211. debug(duration.count(), " ┬Ás!");
  212. return 0;
  213. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement