fork(3) download
copy 
  1. #include<cstdio>
  2. #include<vector>
  3. using namespace std;
  4.  
  5. int N,K;
  6. inline int min(int a,int b){return a>b?b:a;}
  7. inline int max(int a,int b){return a>b?a:b;}
  8.  
  9. const int maxn=1000000;
  10. int data[2*maxn],deque_min[2*maxn],deque_max[2*maxn],M[maxn];
  11.  
  12. int main(){
  13. 	//var;
  14. 	int pivot,i,j,c;
  15.  
  16. 	//code
  17. 	scanf("%d %d",&N,&K);	
  18.  
  19. 	for(i=0;i<N;i++)
  20. 		scanf("%d",&data[i]);
  21.  
  22. 	for(c=0,pivot=K-1;pivot<N;pivot+=K){
  23. 		deque_max[K-1]=deque_min[K-1]=data[pivot];
  24.  
  25. 		for(i=1;i<K;i++){
  26. 			deque_min[K-i-1]=min(deque_min[K-i],data[pivot-i]);
  27. 			deque_max[K-i-1]=max(deque_max[K-i],data[pivot-i]);
  28.  
  29. 			if(pivot+i-1 >= N-1) {
  30. 				deque_max[K+i-1]=deque_min[K+i-1]=0x7fffffff;
  31. 			}
  32. 			else {
  33. 				deque_min[K+i-1]=min(deque_min[K+i-2],data[pivot+i]);
  34. 				deque_max[K+i-1]=max(deque_max[K+i-2],data[pivot+i]);
  35. 			}
  36. 		}
  37. 		for(i=0,j=K-1;i<K;++i,++j){
  38. 			if(++c > N-K+1) break;	
  39. 			M[c-1]=max(deque_max[i],deque_max[j]);
  40. 			printf("%d ",min(deque_min[i],deque_min[j]));
  41. 		}
  42. 	}
  43. 	printf("\n");
  44. 	for(i=0;i<N-K+1;++i)
  45. 		printf("%d ",M[i]);
  46.  
  47. 	return 0;
  48. }
Time limit exceeded #stdin #stdout 5s 30200KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/sduj2J
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

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!