fork download
copy 
  1. __author__ = "Achut"
  2.  
  3. from math import log
  4.  
  5.  
  6. class Node:
  7.     def __init__(self):
  8.         self.sum = -15000
  9.         self.max = -15000
  10.         self.maxR = -15000
  11.         self.maxL = -15000
  12.  
  13.  
  14. def seg_init(node, b, e, A, M):
  15.     if node is 4:
  16.         print("the node is ",M[node].sum)
  17.     if b is e:
  18.         M[node].sum = M[node].max = M[node].maxR = M[node].maxL = A[b]
  19.         print(node, M[node].sum,A[b])
  20.     else:
  21.         seg_init(2 * node, b, (b + e) / 2, A, M)
  22.         seg_init(2 * node + 1, (b + e) / 2 + 1, e, A, M)
  23.         print("booo")
  24.         print node,M[2*node].sum,2*node,M[node].sum
  25.         M[node].sum = M[2*node].sum + M[2*node + 1].sum
  26.         M[node].max = max(M[2*node].max,M[2*node +1].max,M[2*node].maxR+M[2*node+1].maxL)
  27.         M[node].maxR = max(M[node * 2 + 1].maxR, M[node * 2 + 1].sum + M[node * 2].maxR)
  28.         M[node].maxL = max(M[2*node + 1].maxL + M[2*node].sum , M[2*node].maxL)
  29.         print node,M[2*node].sum,2*node,M[node].sum
  30.         print("boooo over")
  31.  
  32. def query(node, b, e, A, M, i, j):
  33.     if b >= i and e <= j:
  34.         return M[node]
  35.     mid = (b + e) / 2
  36.     if j <= mid:
  37.         return query(2 * node, b,mid , A, M, i, j)
  38.     if i > mid:
  39.         return query(2 * node + 1, mid + 1, e, A, M, i, j)
  40.  
  41.     p1 = query(2 * node, b,mid , A, M, i, j)
  42.     p2 = query(2 * node + 1, mid + 1, e, A, M, i, j)
  43.  
  44.     result = Node()
  45.  
  46.     result.sum = M[p1].sum + M[p2].sum
  47.     result.max = max(M[p1].max,M[p2].max,M[p1].maxR+M[p2].maxL)
  48.     result.maxR = max(M[p2].maxR, M[p2].sum + M[p1].maxR)
  49.     result.maxL = max(M[p2].maxL + M[p1].sum , M[p1].maxL)
  50.  
  51.     return result
  52.  
  53. n = int(raw_input().strip())
  54. M = [Node()] * (4 * 50005)
  55. #print("length",len(M))
  56. A = map(int, raw_input().strip().split())
  57. print A
  58.  
  59. seg_init(1, 0, n - 1, A, M)
  60. #for item in M:
  61. #    print item.sum
  62.  
  63. t = int(raw_input().strip())
  64.  
  65. while t:
  66.     t = t - 1
  67.     i, j = map(int, raw_input().strip().split())
  68.     print query(1, 0, n - 1, A, M, i - 1, j - 1).max
  69.  
Success #stdin #stdout 0.02s 7900KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
[-1, 2, 3]
('the node is ', -15000)
(4, -1, -1)
(5, 2, 2)
booo
2 2 4 2
2 4 4 4
boooo over
(3, 3, 3)
booo
1 3 2 3
1 6 2 6
boooo over
6
https://ideone.com/5dhFQa
language:
Python (cpython 2.7.16)
created:
9 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!