fork download
  1. /*
  2.   Compete against Yourself.
  3.   Author - Aryan (@aryanc403)
  4. */
  5. /*
  6.   Credits -
  7.   Atcoder library - https://a...content-available-to-author-only...b.io/ac-library/production/document_en/ (namespace atcoder)
  8.   Github source code of library - https://g...content-available-to-author-only...b.com/atcoder/ac-library/tree/master/atcoder
  9. */
  10.  
  11. #ifdef ARYANC403
  12. #include <header.h>
  13. #else
  14. #pragma GCC optimize ("Ofast")
  15. #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  16. #pragma GCC optimize ("-ffloat-store")
  17. #include<bits/stdc++.h>
  18. #include <ext/pb_ds/assoc_container.hpp>
  19. #include <ext/pb_ds/tree_policy.hpp>
  20. #define dbg(args...) 42;
  21. #define endl "\n"
  22. #endif
  23.  
  24. // y_combinator from @neal template https://c...content-available-to-author-only...s.com/contest/1553/submission/123849801
  25. // http://w...content-available-to-author-only...d.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
  26. template<class Fun> class y_combinator_result {
  27. Fun fun_;
  28. public:
  29. template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
  30. template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
  31. };
  32. template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
  33.  
  34. using namespace std;
  35. #define fo(i,n) for(i=0;i<(n);++i)
  36. #define repA(i,j,n) for(i=(j);i<=(n);++i)
  37. #define repD(i,j,n) for(i=(j);i>=(n);--i)
  38. #define all(x) begin(x), end(x)
  39. #define sz(x) ((lli)(x).size())
  40. #define pb push_back
  41. #define mp make_pair
  42. #define X first
  43. #define Y second
  44.  
  45. typedef long long int lli;
  46. typedef long double mytype;
  47. typedef pair<lli,lli> ii;
  48. typedef vector<ii> vii;
  49. typedef vector<lli> vi;
  50. template <class T>
  51. using ordered_set = __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
  52. // X.find_by_order(k) return kth element. 0 indexed.
  53. // X.order_of_key(k) returns count of elements strictly less than k.
  54.  
  55. const auto start_time = std::chrono::high_resolution_clock::now();
  56. void aryanc403()
  57. {
  58. #ifdef ARYANC403
  59. auto end_time = std::chrono::high_resolution_clock::now();
  60. std::chrono::duration<double> diff = end_time-start_time;
  61. cerr<<"Time Taken : "<<diff.count()<<"\n";
  62. #endif
  63. }
  64.  
  65. const lli INF = 0xFFFFFFFFFFFFFFFLL;
  66. const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
  67. mt19937 rng(SEED);
  68. inline lli rnd(lli l=0,lli r=INF)
  69. {return uniform_int_distribution<lli>(l,r)(rng);}
  70.  
  71. class CMP
  72. {public:
  73. bool operator()(ii a , ii b) //For min priority_queue .
  74. { return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y )); }};
  75.  
  76. void add( map<lli,lli> &m, lli x,lli cnt=1)
  77. {
  78. auto jt=m.find(x);
  79. if(jt==m.end()) m.insert({x,cnt});
  80. else jt->Y+=cnt;
  81. }
  82.  
  83. void del( map<lli,lli> &m, lli x,lli cnt=1)
  84. {
  85. auto jt=m.find(x);
  86. if(jt->Y<=cnt) m.erase(jt);
  87. else jt->Y-=cnt;
  88. }
  89.  
  90. bool cmp(const ii &a,const ii &b)
  91. {
  92. return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
  93. }
  94.  
  95. const lli mod = 1000000007L;
  96. // const lli maxN = 1000000007L;
  97.  
  98. lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
  99. lli m;
  100. string s;
  101. vi a;
  102. //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .
  103.  
  104. int main(void) {
  105. ios_base::sync_with_stdio(false);cin.tie(NULL);
  106. // freopen("txt.in", "r", stdin);
  107. // freopen("txt.out", "w", stdout);
  108. // cout<<std::fixed<<std::setprecision(35);
  109. cin>>T;while(T--)
  110. {
  111.  
  112. cin>>n>>m;
  113. vi a(n);
  114. set<lli> possibleTimes;
  115. map<lli,vii> changes;
  116. const lli placeHolder=-INF;
  117. for(auto &x:a){
  118. cin>>x;
  119. possibleTimes.insert(x/m);
  120. changes[0].pb({placeHolder,x/m});
  121. const lli r=m-(x%m);
  122. if(r==m)
  123. continue;
  124. possibleTimes.insert((x+r)/m);
  125. changes[r].pb({x/m,(x+r)/m});
  126. }
  127. dbg(a,m);
  128. set<lli> currentStreak;
  129.  
  130. for(auto x:possibleTimes){
  131. currentStreak.insert(x-1);
  132. currentStreak.insert(x+1);
  133. currentStreak.insert(x);
  134. }
  135.  
  136. map<lli,lli> mm;
  137. const auto update=[&](const lli u,const lli v){
  138. mm[u]+=v;
  139. if(mm[u]==0)
  140. currentStreak.insert(u);
  141. else if(currentStreak.count(u))
  142. currentStreak.erase(u);
  143. };
  144.  
  145. ii ans={-1,-1};
  146. const auto chk=[&](const lli t,const lli pos){
  147. auto it=currentStreak.lower_bound(pos);
  148. auto jt=it;--jt;
  149. const lli len=(*it)-(*jt)-1;
  150. dbg(len,t);
  151. if(len>ans.X)
  152. ans={len,t};
  153. };
  154.  
  155. for(const auto &z:changes){
  156. const auto &v=z.Y;
  157. const auto t=z.X;
  158.  
  159. for(auto x:v){
  160. if(x.X!=placeHolder)
  161. update(x.X,-1);
  162. update(x.Y,1);
  163. }
  164. dbg(t,v,currentStreak);
  165. for(auto x:v){
  166. if(x.X!=placeHolder)
  167. chk(t,x.X);
  168. chk(t,x.Y);
  169. }
  170. }
  171. dbg(ans);
  172. cout<<ans.X<<" "<<ans.Y<<endl;
  173. } aryanc403();
  174. return 0;
  175. }
  176.  
Success #stdin #stdout 0.01s 5364KB
stdin
Standard input is empty
stdout
Standard output is empty