fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct node
  5. {
  6.     int total;
  7.     int left;
  8.     int right; 
  9.     int best;
  10. };
  11.  
  12. struct node* st = new node[4*50000];
  13.  
  14. struct node merge(struct node l1, struct node r1)
  15. {
  16.     struct node ans;
  17.  
  18.     ans.total = l1.total+r1.total;
  19.     ans.left = max(l1.left, l1.total+r1.left);
  20.     ans.right = max(r1.right, r1.total+l1.right);
  21.     ans.best = max(max(l1.best, r1.best), l1.right+r1.left);
  22.     return ans;
  23. }
  24.  
  25. struct node answer(int ss, int se, int l, int r, int i)
  26. {
  27. 	if(r<ss || l>se)
  28. 	{
  29. 	    struct node ret;
  30. 	    ret.total = 0;
  31. 	    ret.left = -999999;
  32. 	    ret.right = -999999;
  33. 	    ret.best = -999999;
  34. 	    return ret;
  35. 	}
  36.  
  37. 	if (l <= ss && r >= se) 
  38.         return st[i];
  39.  
  40.     int mid = ss+(se-ss)/2; 
  41.     struct node l1 = answer(ss, mid, l , r, 2*i+1);
  42.     struct node r1 = answer(mid+1, se, l, r, 2*i+2);
  43.  
  44.     struct node ans = merge(l1, r1);
  45.     return ans;
  46. }
  47.  
  48. void construct(int arr[], int ss, int se, int i)
  49. {
  50. 	if(ss==se)
  51. 	{
  52. 		st[i].total = arr[ss];
  53. 		st[i].left = arr[ss];
  54. 		st[i].right = arr[ss];
  55. 		st[i].best = arr[ss];
  56. 		return ;
  57. 	}
  58.  
  59. 	int mid = ss+(se-ss)/2;
  60.  
  61. 	construct(arr, ss, mid, 2*i+1);
  62. 	construct(arr, mid+1, se, 2*i+2);
  63.  
  64. 	struct node l1 = st[2*i+1];
  65. 	struct node r1 = st[2*i+2];
  66.  
  67.     st[i] = merge(l1, r1);
  68.  
  69. 	return ;
  70. }
  71.  
  72. void constructST(int arr[], int n)
  73. {
  74. 	construct(arr, 0, n-1, 0);
  75. 	return;
  76. } 
  77.  
  78. int main() {
  79.     ios_base::sync_with_stdio(false);
  80. 	cin.tie(NULL);
  81. 	int n;
  82. 	cin>>n;
  83.  
  84.     int arr[n];
  85. 	for(int i=0; i<n ;i++)
  86. 	{
  87. 		cin>>arr[i];
  88. 	}
  89.  
  90. 	int m;
  91. 	cin >>m;
  92.  
  93. 	while(m--)
  94. 	{
  95. 		int x, y;
  96. 		cin >> x>>y;
  97.  
  98. 		constructST(arr, n);
  99.  
  100. 		struct node ans = answer(0 , n-1, x-1 ,y-1, 0);
  101.  
  102. 		cout << max(max(ans.total, ans.best), max(ans.left, ans.right)) <<"\n";
  103. 	}
  104.  
  105. 	return 0;
  106. }
Time limit exceeded #stdin #stdout 5s 4376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/N7ANFD
problem GSS1, based on SPOJ submission 26063864 (CPP), 2020-05-29 19:42:15
language:
C++ (gcc 8.3)
created:
3 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!