fork download
copy 
  1. def main():
  2.     import sys
  3.     input = sys.stdin.read().split()
  4.     idx = 0
  5.     N = int(input[idx])
  6.     idx += 1
  7.     L = []
  8.     R = []
  9.     for _ in range(N):
  10.         l = int(input[idx])
  11.         r = int(input[idx+1])
  12.         L.append(l)
  13.         R.append(r)
  14.         idx += 2
  15.  
  16.     # Compute prefix max L and min R
  17.     prefix_max_L = [0] * (N)
  18.     prefix_min_R = [0] * (N)
  19.     prefix_max_L[0] = L[0]
  20.     prefix_min_R[0] = R[0]
  21.     for i in range(1, N):
  22.         prefix_max_L[i] = max(prefix_max_L[i-1], L[i])
  23.         prefix_min_R[i] = min(prefix_min_R[i-1], R[i])
  24.  
  25.     # Compute suffix max L and min R
  26.     suffix_max_L = [0] * (N)
  27.     suffix_min_R = [0] * (N)
  28.     suffix_max_L[-1] = L[-1]
  29.     suffix_min_R[-1] = R[-1]
  30.     for i in range(N-2, -1, -1):
  31.         suffix_max_L[i] = max(suffix_max_L[i+1], L[i])
  32.         suffix_min_R[i] = min(suffix_min_R[i+1], R[i])
  33.  
  34.     max_sum = 0
  35.  
  36.     # Check all possible splits into prefix and suffix
  37.     for k in range(1, N):
  38.         # Group1: first k elements
  39.         max_L1 = prefix_max_L[k-1]
  40.         min_R1 = prefix_min_R[k-1]
  41.         joy1 = max(0, min_R1 - max_L1 + 1) if min_R1 >= max_L1 else 0
  42.  
  43.         # Group2: remaining elements
  44.         max_L2 = suffix_max_L[k]
  45.         min_R2 = suffix_min_R[k]
  46.         joy2 = max(0, min_R2 - max_L2 + 1) if min_R2 >= max_L2 else 0
  47.  
  48.         current_sum = joy1 + joy2
  49.         if current_sum > max_sum:
  50.             max_sum = current_sum
  51.  
  52.     # Check all possible splits where one group is a single problem
  53.     left_max_L = [0] * (N+2)
  54.     right_max_L = [0] * (N+2)
  55.     left_min_R = [float('inf')] * (N+2)
  56.     right_min_R = [float('inf')] * (N+2)
  57.  
  58.     # Compute left_max_L and left_min_R
  59.     for i in range(1, N+1):
  60.         left_max_L[i] = max(left_max_L[i-1], L[i-1])
  61.         left_min_R[i] = min(left_min_R[i-1], R[i-1])
  62.  
  63.     # Compute right_max_L and right_min_R
  64.     for i in range(N, 0, -1):
  65.         right_max_L[i] = max(right_max_L[i+1], L[i-1])
  66.         right_min_R[i] = min(right_min_R[i+1], R[i-1])
  67.  
  68.     for i in range(1, N+1):
  69.         # max_L_rest is max of left and right parts excluding i
  70.         max_L_rest = max(left_max_L[i-1], right_max_L[i+1])
  71.         min_R_rest = min(left_min_R[i-1], right_min_R[i+1])
  72.         joy_rest = max(0, min_R_rest - max_L_rest + 1) if min_R_rest >= max_L_rest else 0
  73.  
  74.         # joy_i is the single problem's joy
  75.         joy_i = max(0, R[i-1] - L[i-1] + 1) if R[i-1] >= L[i-1] else 0
  76.         current_sum = joy_rest + joy_i
  77.         if current_sum > max_sum:
  78.             max_sum = current_sum
  79.  
  80.     print(max_sum)
  81.  
  82. if __name__ == '__main__':
  83.     main()
Success #stdin #stdout 0.02s 7268KB
comments (?)
stdin
copy 
4
4 7
1 4
5 8
2 5
stdout
copy 
5
https://ideone.com/tQI2eI
language:
Python (cpython 2.7.16)
created:
1 day 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!