CFR 777 C. Alyona and Spreadsheet ( Python Output Optimization )

Problem - C - Codeforces

題意：
給一個 N * M 的矩陣。K 筆詢問，每次問 [ L, R ] 範圍的行是否存在一個列，使得在 [ L, R ] 之間為非遞減。

資料規模：
The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.
Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for ai, j (1 ≤ ai, j ≤ 1e9).
The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.
The i-th of the next k lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n).

解法：
對於每個列，由下到上預處理最長可以延伸多長。接著分別對每個行記錄該行內可以伸的最遠長度。對於一筆詢問，只要問行 L 中可以伸得最遠的長度是否為 R - L + 1 以上即可。如果用 Python 寫，會被卡輸出速度，這部分要用 sys.stdout.write 進行優化。

時間 / 空間複雜度：
O( N * M )

import sys

N, M = map( int, input().split() )
G = [ list( map( int, input().split() ) ) for i in range( N ) ]

rmaxv = [ 0 for i in range( N ) ]
for i in range( M ):
  reach = [ 0 for j in range( N ) ]
  for j in range( N - 1, -1, -1 ):
    if j + 1 == N or not ( G[ j ][ i ] <= G[ j + 1 ][ i ] ):
      reach[ j ] = 1
    else:
      reach[ j ] = reach[ j + 1 ] + 1
    rmaxv[ j ] = max( rmaxv[ j ], reach[ j ] )

Q = int( input() )
ans = []
for qi in range( Q ):
  L, R = map( int, input().split() )
  if rmaxv[ L - 1 ] >= R - L + 1:
    ans.append( "Yes\n" )
  else:
    ans.append( "No\n" )

sys.stdout.write( ''.join( ans ) )