fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ch3nYv
language:
C++14 (gcc 8.3)
created:
2 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!