fork download
copy 
  1. /***********************
  2. *   Jay Prakash Mahto  *
  3. *       JVJplus        *
  4. ************************/
  5.  
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define For(i,n) for(int i=0;i<n;i++)
  10. #define FOR(i,a,b) for(int i=a;i<=b;i++)
  11. #define ll long long int
  12. #define pii pair<int,int>
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define vi vector<int> 
  17. #define REMAX(a,b) a=max(a,b) 
  18. #define N 200005
  19. #define MOD 1000000007 //check it 
  20. #define dbg(x) cerr<<#x<<" "<<x<<endl;
  21.  
  22. //make ipow and ms0
  23. //think of segtree / sqrt decom.
  24.  
  25. int n,bct_sz;
  26. int arr[N];
  27. int lazy[N];
  28. int maxBucket[N];
  29.  
  30.  
  31. void init(){
  32. 	bct_sz=sqrt(n);
  33. 	For(i,n){
  34. 		REMAX(maxBucket[i/bct_sz],arr[i]);
  35. 	}
  36. }
  37.  
  38. void update(int l,int r,int value){
  39. 	int b1=l/bct_sz;
  40. 	int b2=r/bct_sz;
  41.  
  42. 	if(b1==b2){
  43. 		FOR(i,l,r)
  44. 			arr[i]+=value;
  45.  
  46. 		int mx=-1;
  47. 		FOR(i,b1*bct_sz,(b1+1)*bct_sz-1)
  48. 			REMAX(mx,arr[i]);
  49. 		maxBucket[b1]=mx;
  50. 		return;
  51. 	}
  52.  
  53. 	//starting
  54. 	while(l!=0 && l%bct_sz!=0){
  55. 		arr[l]+=value;
  56. 		l++;
  57. 	}
  58. 	int mx=-1;
  59. 	FOR(i,b1*bct_sz,(b1+1)*bct_sz-1)
  60. 		REMAX(mx,arr[i]);
  61. 	maxBucket[b1]=mx;
  62.  
  63. 	//middle
  64. 	while(l<=r){
  65. 		lazy[l/bct_sz]+=value;
  66. 		l+=bct_sz;
  67. 	}
  68.  
  69. 	//ends
  70. 	mx=-1;
  71. 	while(l<=r) {
  72. 		arr[l]+=value;
  73. 		REMAX(mx,arr[l]);
  74. 	    l++;
  75. 	}
  76.  
  77. 	while(l<b2*bct_sz){
  78. 		REMAX(mx,arr[l]);
  79. 		l++;
  80. 	}
  81. 	maxBucket[b2]=mx;	
  82. }
  83.  
  84. int queryMAX(int l,int r){
  85. 	int mx = -1;
  86. 	int len=bct_sz;
  87. 	int c_l = l / len,   c_r = r / len;
  88. 	if (c_l == c_r)
  89. 	    for (int i=l; i<=r; ++i)
  90. 	        REMAX(mx,arr[i]+lazy[c_l]);
  91. 	else {
  92. 	    for (int i=l, end=(c_l+1)*len-1; i<=end; ++i)
  93. 	        REMAX(mx,arr[i]+lazy[i/bct_sz]);
  94. 	    for (int i=c_l+1; i<=c_r-1; ++i)
  95. 	        REMAX(mx,maxBucket[i]+lazy[i]);
  96. 	    for (int i=c_r*len; i<=r; ++i)
  97. 	        REMAX(mx,arr[i]+lazy[i/bct_sz]);	    
  98. 	}
  99.  
  100. 	return mx;
  101. }
  102.  
  103. void printStatus(){
  104. 	For(i,n){
  105. 		cerr<<arr[i]+lazy[i/bct_sz]<<" ";
  106. 	}
  107. 	cerr<<endl;
  108. }
  109.  
  110. void solve(){
  111. 	cin>>n;
  112. 	For(i,n){
  113. 		cin>>arr[i];
  114. 	}        
  115. 	init();
  116.  
  117. 	int mx=0;
  118. 	For(i,n){
  119. 		arr[i]+=(i+1);
  120. 		REMAX(mx,arr[i]);
  121. 	}
  122. 	cout<<mx<<" ";
  123.  
  124. 	init();
  125.  
  126. 	for(int i=n-1;i>0;i--){
  127. 		//reduce ith by N
  128. 		update(i,i,-n);
  129. 		//update all by 1
  130. 		update(0,n-1,+1);
  131. 		cout<<queryMAX(0,n-1)<<" ";
  132.  
  133. 		// printStatus();
  134. 	}
  135.  
  136. }
  137.  
  138.  
  139. int main(){
  140.  
  141.     ios_base::sync_with_stdio(false);
  142.     cin.tie(NULL);
  143.     cout.tie(NULL);
  144.  
  145.     { 
  146.         solve();   
  147.     }
  148.  
  149. }
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FaTfjP
4
7 1 6 2
language:
C++14 (gcc 8.3)
created:
5 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!