fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. const int MX=200003;
  5. #define endl "\n"
  6. #define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
  7. ll tree[1010000];
  8. ll arr[MX];
  9. ll marked[1010000];
  10. ll n,var;
  11. #define inf 9223372036854775807
  12.  
  13. void build(ll node, ll low, ll high){
  14. 	if(low == high){
  15. 		tree[node] = arr[low];
  16. 		return;
  17. 	}
  18.  
  19. 	ll mid = (low+high)/2; 
  20. 	build(2*node,low,mid);
  21. 	build(2*node+1,mid+1,high);
  22.  
  23. 	tree[node] = min(tree[2*node],tree[2*node+1]);
  24.  
  25. }
  26.  
  27. void update(ll node, ll low,ll high,ll l, ll r, ll val){
  28.  
  29.  
  30. 	if(r<l) return;
  31.  
  32. 	if(marked[node]!=0){
  33. 		tree[node] += marked[node];
  34. 		if(low !=high){
  35. 			marked[2*node] += marked[node];
  36. 			marked[2*node+1] += marked[node];	
  37. 		}
  38.  
  39. 		marked[node] = 0;
  40. 	}
  41.  
  42. 	if(low ==l && high == r){
  43. 		tree[node]+= val;
  44. 		if(low != high){
  45. 			marked[2*node] += val;
  46. 			marked[2*node+1] += val;	
  47. 		}	
  48. 		return;
  49. 	}
  50.  
  51.  
  52. 	ll mid = (low+high)/2;
  53.  
  54. 	update(2*node,low,mid,l,min(r,mid),val);
  55. 	update(2*node+1,mid+1,high,max(mid+1,l),r,val);
  56.  
  57. 	tree[node] = min(tree[2*node],tree[2*node+1]);
  58. }
  59.  
  60. ll query(ll node, ll low, ll high, ll l, ll r){
  61.  
  62.  
  63. 	if(r<l) return inf;
  64.  
  65. 	if(marked[node]){
  66. 		tree[node] += marked[node];
  67. 		if(low !=high){
  68. 			marked[2*node] += marked[node];
  69. 			marked[2*node+1] += marked[node];	
  70. 		}	
  71. 		marked[node] = 0;
  72. 	}
  73.  
  74.  
  75. 	if(low == l && high == r){
  76. 		return tree[node];
  77. 	}
  78.  
  79. 	ll mid = (low+high)/2;
  80.  
  81. 	ll left = query(2*node,low,mid,l,min(r,mid));
  82. 	ll right = query(2*node+1,mid+1,high,max(mid+1,l),r);
  83.  
  84. 	return min(left,right);
  85.  
  86. }
  87.  
  88.  
  89. int main(){
  90. 	FIO;
  91. 	// freopen("input.txt", "r", stdin);
  92. 	// freopen("output.txt", "w", stdout);
  93.  
  94.    	cin>>n;
  95.    	for(int i=1;i<=n;i++){
  96.    		cin>>arr[i];
  97.    	}
  98.  
  99.    	build(1,1,n);
  100.  
  101.    	ll q;
  102.    	cin>>q;
  103.    	ll cnt = 1;
  104.    	while(q){
  105.    		vector<int> v;
  106.    		string str;
  107.    		getline(cin, str);
  108.    		stringstream ss(str);
  109.  
  110. 		// cout<<str<<endl;   		
  111.    		while(ss >> var)
  112.    			v.push_back(var);
  113.  
  114.    		if(v.size() == 0) continue;
  115.    		// cout<<v.size()<<endl;
  116.  
  117. 		ll l = v[0] + 1;
  118. 		ll r = v[1] + 1;
  119.  
  120. 		if(v.size() == 3){
  121.  
  122. 			// cout<<v[2]<<endl;
  123. 			if(r<l){
  124. 				update(1,1,n,l,n,v[2]);
  125. 				update(1,1,n,1,r,v[2]);
  126. 			}
  127. 			else{
  128. 				update(1,1,n,l,r,v[2]);	
  129. 			} 
  130.  
  131.  
  132. 		}
  133. 		else{
  134.  
  135. 			if(r<l){
  136. 				ll ans1 = query(1,1,n,l,n);
  137. 				ll ans2 = query(1,1,n,1,r);
  138. 				cout<<min(ans1,ans2)<<endl;
  139. 			}
  140. 			else{
  141. 				cout<<query(1,1,n,l,r)<<endl;
  142. 			}
  143.  
  144. 		}
  145.  
  146. 		cout<<"cnt = "<<cnt++<<endl;
  147. 		for(int i=1;i<=7;i++){
  148. 			cout<<i<<"="<<tree[i]<<" ";
  149. 		}
  150. 		cout<<endl;
  151. 		for(int i=1;i<=7;i++){
  152. 			cout<<i<<"="<<marked[i]<<" ";	
  153. 		}
  154. 		cout<<endl;
  155. 		q--;
  156.    	}
  157.  
  158.  
  159.     return 0;
  160. }
Internal error #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1xLDk5
language:
C++14 (gcc 8.3)
created:
3 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!