fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3. #define ld long double
  4. #define nl "\n"
  5. #define ull unsigned long long
  6. #define rv return void
  7. #define str string
  8. #define all(x) x.begin(), x.end()
  9. #define allr(x) x.rbegin(), x.rend()
  10. #define vec vector
  11. #define fixed(n) fixed << setprecision(n)
  12. #define Moageza ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
  13. using namespace std;
  14. const ll mod = 1e9+7;
  15. //////////////////////////////////////////////////////
  16. struct SegmentTree{
  17. private:
  18. #define L 2*node+1
  19. #define R 2*node+2
  20. #define mid (l+r>>1)
  21. struct Node{
  22.     ll sum{}, ans{}, mx_pref{}, mx_suff{};
  23.     Node() {}
  24.     Node(ll val) {
  25.         sum = val;
  26.         ans = mx_pref = mx_suff = val;
  27. };
  28. };
  29. Node merge(Node x, Node y){
  30.     Node res;
  31.       res.sum = x.sum + y.sum;
  32.       res.ans = max({x.ans, y.ans, x.mx_suff + y.mx_pref});
  33.       res.mx_pref = max(x.mx_pref, x.sum + y.mx_pref);
  34.       res.mx_suff = max(y.mx_suff, y.sum + x.mx_suff);
  35.       return res;
  36.   }
  37.     int sz;vector<Node>seg;
  38.     void update(int l,int r,int node,int idx,ll val)
  39.     {
  40.         if(l==r)
  41.         {
  42.             seg[node]=Node(val);
  43.             return;
  44.         }
  45.         if(idx<=mid)
  46.         {
  47.             update(l,mid,L,idx,val);
  48.         }
  49.         else
  50.         {
  51.             update(mid+1,r,R,idx,val);
  52.         }
  53.         seg[node]=merge(seg[L],seg[R]);
  54.     }
  55.     Node query(int l,int r,int node,int lq,int rq)
  56.     {
  57.         if(r<lq||l>rq)
  58.         {
  59.             return Node(-1e12);
  60.         }
  61.         if(l>=lq&&r<=rq)
  62.         {
  63.             return seg[node];
  64.         }
  65.         Node lft=query(l,mid,L,lq,rq);
  66.         Node rgt=query(mid+1,r,R,lq,rq);
  67.         return merge(lft,rgt);
  68.     }
  69. public:
  70.     SegmentTree(int n)
  71.     {
  72.         sz=1;
  73.         while(sz<n) sz*=2;
  74.         seg=vector<Node>(sz*2);
  75.     }
  76.     void update(int idx,ll val)
  77.     {
  78.         update(0,sz-1,0,idx,val);
  79.     }
  80.     ll query(int l,int r)
  81.     {
  82.         return query(0,sz-1,0,l,r).ans;
  83.     }
  84. };
  85. void solve(){
  86.      int a,b;cin >> a;
  87.    SegmentTree st(a);
  88.    for(int i=0;i<a;i++){
  89.     int x;cin >> x;
  90.     st.update(i,x);
  91.    }
  92.    cin>> b;
  93.    for(int i=0;i<b;i++){
  94.     int x,y;cin >>x>>y;
  95.     cout <<st.query(x-1,y-1)<<nl;
  96.    }
  97. }
  98. int main()
  99. {
  100.    Moageza
  101.     #ifndef ONLINE_JUDGE
  102.         freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
  103.     #endif
  104.     int t = 1;
  105.     //  cin >> t;
  106.     while (t--) {
  107.         solve();
  108.         cout << nl;
  109.     }
  110.     return 0;
  111. }
Success #stdin #stdout 0s 5264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/Aok1kV
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
9 days 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!