Observation

The position of the maximum value in the array never changes. If an element is the maximum at the start, it will continue to be the maximum after any number of operations.

Why?

• The operations only increment or decrement the elements within a given range.
• If the current maximum is not within the range of an operation, it remains unchanged.
• If the current maximum is within the range, it either increases by 1 (for + l r) or decreases by 1 (for - l r).

Approach

• Initialize:

  • Find the initial maximum value of the array and store it as curr_max.

• Process Each Operation:

  • For each operation, check if curr_max lies within the range [l, r].
  • If curr_max is within the range:
    • If the operation is + l r, increment curr_max by 1.
    • If the operation is - l r, decrement curr_max by 1.
  • If curr_max is not within the range, it remains unchanged.

• Collect Results:

  • Store the current maximum after each operation.

• Output:

  • Print the maximum value after each operation for each test case.

Complexity Analysis:

• Time Complexity: O(n + m) per test case:
• O(n) for finding the initial maximum.
• O(m) for processing the operations.
• Space Complexity: O(m) for storing the result.

import sys 
input = sys.stdin.readline 

def solve():
    n, m = map(int, input().split())
    nums = list(map(int, input().split()))
    result, curr_max = [0] * m, max(nums) 

    for i in range(m):
        op, l, r = map(str, input().split())
        if int(l) <= curr_max <= int(r):
            if op == '+':
                curr_max += 1
                result[i] = curr_max
            else:
                curr_max -= 1
                result[i] = curr_max
            
            continue
        
        result[i] = curr_max

    print(*result)

if __name__ == '__main__':
    for _ in range(int(input())):
        solve()

According to the statement, to the left of the road there should be no less elements ai such that ai=0 than such that ai=1 , and to the right of the road there should be no less elements ai than such that ai=1 than such that ai=0 .

We will consider each position of the road and check the compliance with the road design condition. To do this, we will use the prefix sum method to access the number of 1 's in the suffix in O(1) (the number of such i that i>x and ai=1 for any x ). We will also maintain the count of 0 's among the elements to the left of the road and the optimal answer. If the road position x is suitable and it is closer to the middle than the most optimal answer found before, we will update it (and will not forget to increase the count of 0 if the next element ax+1=0 ).

It is convenient to double the distance to the middle of the village: instead of ∣∣n2−i∣∣ , consider it as 2∣∣n2−i∣∣=|n−2⋅i| . This way, we can get rid of calculations in non-integer numbers.

Complexity: O(n)

for case in range(int(input())):
    n = int(input())
    a = input()
    suf_cnt = [0] * (n + 1)
    for i in range(n — 1, -1, -1):
        suf_cnt[i] = suf_cnt[i + 1] + (a[i] == '1')
    pref_cnt = 0
     
    opt_ans = -1
    opt_dist = n * 2
    threshold = (n + 1) // 2
     
    for i in range(n + 1):
        if pref_cnt >= (i + 1) // 2 and suf_cnt[i] >= (n - i + 1) // 2 and abs(n - 2 * i) < opt_dist:
            opt_dist = abs(n - 2 * i)
            opt_ans = i
        if i != n:
            pref_cnt += (a[i] == '0')
     
    print(opt_ans)

Let us describe each cell of the field by four numbers (xb, yb, xs, ys), 0 ≤ xb, yb, xs, ys ≤ 2), where (xb, yb) are coordinates of small field containing the cell, and (xs, ys) are coordinates of the cell in it's small field. It can be seen that for cell with "usual" coordinates (x, y), 1 ≤ x, y ≤ 9 and our new (xb, yb, xs, ys), there are following equalities which give us a key to go between coordinate systems:

xb = ⌊((x - 1) / 3)⌋, yb = ⌊((y - 1) / 3)⌋; xs = (x - 1) mod 3, yb = (y - 1) mod 3; x = 3 * xb + xs + 1, y = 3 * yb + ys + 1. In terms of new coordinates, if last move was in cell (xb, yb, xs, ys), then next move should be in arbitrary free cell with coordinates (xs, ys, x', y') for some if it's possible; otherwise, next move can be done in arbitrary free cell. To solve the problem, one can go through all such pairs (x', y') and write "!" in each empty cell (xs, ys, x', y'); if there are not such empty cells, write "!" in all empty cells of the field.

grid = []
#taking input
for i in range(11):
    #removing the space inbetween
    line = ''.join(input().split())

    #ignoring empty lines
    if line == "":
        continue

    grid.append(list(line))


x,y  = map(int,input().split())

#calculating the start of the box of the next move using the last input
startr = (((x-1)%3))*3
startc = (((y-1)%3))*3

#iterating through the valid cells inside the box and modifiying if they're available
flag = False
for i in range(startr,startr+3):
    for j in range(startc,startc+3):
        if grid[i][j] =='.':
            flag = True
            grid[i][j] = '!'

# if there were no available cell in the box then we can move anywhere so mark all available spots
if not flag:
    for i in range(9):
        for j in range(9):
            if grid[i][j] == '.':
                grid[i][j] ='!'

# since we removed all the empty spaces that are also required in the final output
# we need to reinsert them in final output 
ans = []
for i in range(11):
    if i == 3 or i == 7:
        ans.append('')
    else:
        curr = []
        for j in range(11):
            if j == 3 or j == 7:
                curr.append(' ')
            else:
                curr.append(grid[i-(i//4)][j-(j//4)])
        ans.append(curr)

#output the answer
for line in ans:
    print(''.join(line))