fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef int64_t ll;
  5. typedef uint64_t ull;
  6. typedef long double ld;
  7. typedef pair<int,int> pii;
  8. typedef pair<ll,ll> pll;
  9. typedef vector<int> vi;
  10. #define sf scanf
  11. #define pf printf
  12. #define nl printf("\n")
  13. #define si(x) scanf("%d",&x)
  14. #define sii(x,y) scanf("%d%d",&x,&y)
  15. #define siii(x,y,z) scanf("%d%d%d",&x,&y,&z)
  16. #define sl(x) scanf("%lld",&x)
  17. #define sll(x,y) scanf("%lld%lld",&x,&y)
  18. #define slll(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
  19. #define FOR(i,n) for(int i=0;i<n;i++)
  20. #define sz(x) (int)x.size()
  21. #define all(x) x.begin(),x.end()
  22. #define chk cerr<<"CAME HERE"<<endl
  23. #define dbug(x) cerr<<"value of "<<#x<<" = "<<x<<endl
  24. mt19937_64 rng((uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count());
  25. inline ll rand(ll l, ll r){uniform_int_distribution<ll> RNG(l,r);return RNG(rng);}
  26. template<typename T>inline void togglebit(T &x, int pos){x^=(T(1)<<pos);}
  27. template<typename T>inline bool chkbit(T x, int pos){return bool(x&(T(1)<<pos));}
  28. template<typename T>inline void setbit(T &x, int pos){x|=(T(1)<<pos);}
  29. template<typename T>inline void resetbit(T &x, int pos){if(chkbit(x,pos))togglebit(x,pos);}
  30.  
  31.  
  32. const int N = 1e5+5;
  33.  
  34.  
  35. void work(vector<int>& arr, int k) {
  36. vector<int>ans;
  37. multiset<int>R,L;
  38.  
  39. auto balance = [&](){
  40. if(L.size() > R.size()+1){
  41. R.insert(*L.rbegin());
  42. L.erase(L.find(*L.rbegin()));
  43. }
  44. if(R.size() > L.size()){
  45. L.insert(*R.begin());
  46. R.erase(R.begin());
  47. }
  48. };
  49.  
  50. auto Del = [&](int x){
  51. if(L.count(x))L.erase(L.find(x));
  52. else R.erase(R.find(x));
  53. balance();
  54. };
  55.  
  56. for(int i=0,n=sz(arr),x; i<n; i++){
  57. x=arr[i];
  58. if(L.empty())L.insert(x);
  59. else if(*L.rbegin()>x)L.insert(x);
  60. else R.insert(x);
  61. balance();
  62.  
  63.  
  64. if(sz(L)+sz(R)==k){
  65. pf("%d ",*L.rbegin());
  66.  
  67. x=arr[i-k+1];
  68. Del(x);
  69. // if(L.count(x))L.erase(L.find(x));
  70. // else R.erase(R.find(x));
  71. // balance();
  72. }
  73. }
  74.  
  75.  
  76.  
  77. }
  78.  
  79. void solve(int casenum){
  80. int n,k;
  81. sii(n,k);
  82. vi arr(n);
  83. FOR(i,n)si(arr[i]);
  84. work(arr,k);
  85.  
  86. }
  87.  
  88. int main(){
  89. //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  90. //freopen("input.txt","r",stdin);
  91. //freopen("output.txt","w",stdout);
  92. int T=1;
  93. //scanf("%d",&T);
  94. //cin>>T;
  95. for(int i=1; i<=T; i++)
  96. solve(i);
  97.  
  98. return 0;
  99. }
Runtime error #stdin #stdout 0.69s 2089676KB
stdin
Standard input is empty
stdout
Standard output is empty