Problem:


Score : 1000 points

Problem Statement

You are given a sequence a = \{a_1, ..., a_N\} with all zeros, and a sequence b = \{b_1, ..., b_N\} consisting of 0 and 1. The length of both is N.

You can perform Q kinds of operations. The i-th operation is as follows:

Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.

Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.

Constraints

1 \leq N \leq 200,000

b consists of 0 and 1.

1 \leq Q \leq 200,000

1 \leq l_i \leq r_i \leq N

If i \neq j, either l_i \neq l_j or r_i \neq r_j.

Input

Input is given from Standard Input in the following format:

N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print the minimum possible hamming distance.

Sample Input 1

3
1 0 1
1
1 3

Sample Output 1

1

If you choose to perform the operation, a will become \{1, 1, 1\}, for a hamming distance of 1.

Sample Input 2

3
1 0 1
2
1 1
3 3

Sample Output 2

0

If both operations are performed, a will become \{1, 0, 1\}, for a hamming distance of 0.

Sample Input 3

3
1 0 1
2
1 1
2 3

Sample Output 3

1

Sample Input 4

5
0 1 0 1 0
1
1 5

Sample Output 4

2

It may be optimal to perform no operation.

Sample Input 5

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7

Sample Output 5

3

Sample Input 6

15
1 1 0 0 0 0 0 0 1 0 1 1 1 0 0
9
4 10
13 14
1 7
4 14
9 11
2 6
7 8
3 12
7 13

Sample Output 6

5

Sample Input 7

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9

Sample Output 7

1



Sample input:
3
1 0 1
1
1 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
class segment_tree:
    def __init__(self, N, operator_M, e_M):
        self.op_M = operator_M
        self.e_M = e_M
        
        self.N0 = 1<<(N-1).bit_length()
        self.dat = [self.e_M]*(2*self.N0)
    
    # 長さNの配列 initial で初期化
    def build(self, initial):
        self.dat[self.N0:self.N0+len(initial)] = initial[:]
        for k in range(self.N0-1,0,-1):
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])

    # a_k の値を x に更新
    def update(self,k,x):
        k += self.N0
        self.dat[k] = x
        k //= 2
        while k:
            self.dat[k] = self.op_M(self.dat[2*k], self.dat[2*k+1])
            k //= 2

    # 区間[L,R]をopでまとめる
    def query(self,L,R):
        L += self.N0; R += self.N0 + 1 
        sl = sr = self.e_M
        while L < R:
            if R & 1:
                R -= 1
                sr = self.op_M(self.dat[R],sr)
            if L & 1:
                sl = self.op_M(sl,self.dat[L])
                L += 1
            L >>= 1; R >>= 1
        return self.op_M(sl,sr)

    def get(self, k): #k番目の値を取得。query[k,k]と同じ
        return self.dat[k+self.N0]

# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
*b, = [0]+[*map(int, readline().split())]
q, = map(int, readline().split())

left = [[] for i in range(n+1)]
mp = map(int, read().split())
for l,r in zip(mp,mp):
    left[r].append(l)

from itertools import accumulate
one = list(accumulate(b))

"""
dp[i] = i までみたスコア（同じなら1点）の最大値



"""
dp = segment_tree(n+1,max,0)    

for i in range(1,n+1):
    if left[i]:
        v = min(left[i])
        res = max(one[i] - one[l-1] + dp.query(0,l-1) for l in left[i]) #1にする
        res = max(res, (i-(v-1))-(one[i]-one[v-1]) + dp.query(0,v-1)) #0にする
        dp.update(i, res)
    else:
        res =  (1-b[i]) + dp.query(0,i-1)
        dp.update(i,res)


print(n-dp.get(n))

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

INF = 10**6

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
b = list(map(int, input().split()))
cum = [0]
for x in b:
	if x == 1:
		cum.append(cum[-1] + 1)
	else:
		cum.append(cum[-1])
Q = int(input())
q = sorted([list(map(int, input().split())) for _ in range(Q)], key=lambda x: x[1])

dp = Rmin(n+1)
dp.Update(0, cum[-1])
ans = cum[-1]
for l, r in q:
	mi = dp.Get(0, l)
	num = cum[r] - cum[l-1]
	res = r-l+1 - num*2 + mi
	if dp.Access(r) > res:
		dp.Update(r, res)
		ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

INF = 10**6

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
b = list(map(int, input().split()))
cum = [0]
for x in b:
	if x == 1:
		cum.append(cum[-1] + 1)
	else:
		cum.append(cum[-1])
Q = int(input())
q = sorted([list(map(int, input().split())) for _ in range(Q)], key=lambda x: x[1])

dp = Rmin(n+1)
dp.Update(0, cum[-1])
ans = cum[-1]
for l, r in q:
	mi = dp.Get(0, l)
	num = cum[r] - cum[l-1]
	res = r-l+1 - num*2 + mi
	dp.Update(r, res)
	ans = min(ans, res)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
B = list(map(int,readline().split()))
Q = int(readline())
m = map(int,read().split())
LR = sorted(zip(m,m))

class MaxSegTree():
    def __init__(self,raw_data):
        N = len(raw_data)
        self.size = 1<<(N.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)
        
    def build(self,raw_data):
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
            i >>= 1
    
    def get_data(self,i):
        return self.data[i+self.size]

    def get_max(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 0
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

"""
・あるから先を全て0で埋めた場合
・あるから先を全て1で埋めた場合
"""
add1 = [0] * (N+1)
add1[0] = sum(B)
for i,x in enumerate(B,1):
    if x:
        add1[i] = add1[i-1] - 1
    else:
        add1[i] = add1[i-1]
add0 = [N - i - x for i,x in enumerate(add1)]

add0,add1

# ある場所を最後の右端まで使ったとする。残りを全て 0 / 1 で埋めたときのスコア
dp0 = MaxSegTree([0] * (N+1))
dp1 = MaxSegTree([0] * (N+1))
dp0.update(0,add0[0])
dp1.update(0,add1[0])

for L,R in LR:
    a = dp1.get_data(R)
    b = dp0.get_max(0,L-1) + add1[L-1] - add0[L-1]
    c = dp1.get_data(R)
    if b < c:
        b = c
    if a < b:
        dp1.update(R, b)
        dp0.update(R, b - add1[R] + add0[R])

answer = N - dp0.get_max(0,N)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
B = list(map(int,readline().split()))
Q = int(readline())
m = map(int,read().split())
LR = sorted(zip(m,m))

class MaxSegTree():
    def __init__(self,raw_data):
        N = len(raw_data)
        self.size = 1<<(N.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
            i >>= 1
    
    def get_data(self,i):
        return self.data[i+self.size]

    def get_max(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 0
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

"""
・あるから先を全て0で埋めた場合
・あるから先を全て1で埋めた場合
"""
add1 = [0] * (N+1)
add1[0] = sum(B)
for i,x in enumerate(B,1):
    if x:
        add1[i] = add1[i-1] - 1
    else:
        add1[i] = add1[i-1]
add0 = [N - i - x for i,x in enumerate(add1)]

add0,add1

# ある場所を最後の右端まで使ったとする。残りを全て 0 / 1 で埋めたときのスコア
dp0 = MaxSegTree([0] * (N+1))
dp1 = MaxSegTree([0] * (N+1))
dp0.update(0,add0[0])
dp1.update(0,add0[1])

for L,R in LR:
    a = dp1.get_data(R)
    b = dp0.get_max(0,L-1) + add1[L-1] - add0[L-1]
    c = dp1.get_data(R)
    if b < c:
        b = c
    if a < b:
        dp1.update(R, b)
        dp0.update(R, b - add1[R] + add0[R])

answer = N - dp0.get_max(0,N)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
B = list(map(int,readline().split()))
Q = int(readline())
m = map(int,read().split())
LR = sorted(zip(m,m))

class MaxSegTree():
    def __init__(self,raw_data):
        N = len(raw_data)
        self.size = 1<<(N.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
            i >>= 1
    
    def get_data(self,i):
        return self.data[i+self.size]

    def get_max(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 0
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

"""
・あるから先を全て0で埋めた場合
・あるから先を全て1で埋めた場合
"""
add1 = [0] * (N+1)
add1[0] = sum(B)
for i,x in enumerate(B,1):
    if x:
        add1[i] = add1[i-1] - 1
    else:
        add1[i] = add1[i-1]
add0 = [N - i - x for i,x in enumerate(add1)]

add0,add1

# ある場所を最後の右端まで使ったとする。残りを全て 0 / 1 で埋めたときのスコア
dp0 = MaxSegTree([0] * (N+1))
dp1 = MaxSegTree([0] * (N+1))
dp0.update(0,add0[0])
dp1.update(0,add0[1])

for L,R in LR:
    a = dp1.get_data(R)
    b = dp0.get_max(0,L-1) + add1[L-1] - add0[L-1]
    c = dp1.get_data(R)
    if b < c:
        b = c
    if a < b:
        dp1.update(R, b)
        dp0.update(R, b - add1[R] + add0[R])

answer = N - dp0.get_max(0,N)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
import itertools

N = int(readline())
B = [int(x) for x in readline().split()]
Q = int(readline())
LR = sorted([tuple(int(x) for x in line.split()) for line in readlines()],key=lambda x:x[1])

"""
Rが手前のものから処理。その時点で、Bと一致できているセルの個数を最大化したい
代わりに、「「00000」から見た改善量」をdpとして持つ。
区間[L,R] を最後に使うとき、手前はdp[0,...,L-1]の最大値でとりたい。
よって、dpの区間maxをBITで管理すればよい
"""

# 1とおいたときの改善量
improve_cum = [0] + list(itertools.accumulate(2*x-1 for x in B))

def BIT_update(tree,i,x):
    while i<=N and tree[i] < x:
        tree[i] = x
        i += i&(-i)

def BIT_max(tree,i):
    ret = 0
    while i:
        if ret < tree[i]:
            ret = tree[i]
        i -= i&(-i)
    return ret

dp = [0] * (N+1)

for L,R in LR:
    x = improve_cum[R] - improve_cum[L-1] # 区間[L,R] での改善量
    x += BIT_max(dp,L-1) # [0,L-1]での改善量の最大値
    BIT_update(dp,R,x)

base_score = sum(B)
answer = base_score - max(dp)
print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# coding: utf-8

from sys import stdin

def cost_gain(lr):
  global bs
  l, r = lr
  sb = bs[l - 1 : r]
  cost = sum(1 for b in sb if b == '0')
  gain = sum(1 for b in sb if b == '1')
  return cost, gain

def key(lr):
  cost, gain = cost_gain(lr)
  return (cost, -gain, lr)

def solve(lr):
  global bs
  dist = sum(1 for b in bs if b == '1')
  while True:
    lr.sort(key=key)
    cost, gain = cost_gain(lr[0])
    if cost >= gain: break
    l, r = lr[0]
    for i in range(l - 1, r):
      bs[i] = '*'
    dist += cost - gain
  return dist

N  = int(stdin.readline())
bs = [w for w in stdin.readline().split()]
Q  = int(stdin.readline())
lr = []
for i in range(Q):
  l, r = [int(w) for w in stdin.readline().split()]
  lr.append((l, r))
if len(bs) != N: raise
if len(lr) != Q: raise

print(solve(lr))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(3 * 10**5)

n = int(input())
b = list(map(int, input().split()))
op = [[] for i in range(n)]
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    op[l - 1].append(r)
nula = [0 for i in range(n + 1)]
for i in range(n):
    nula[i + 1] = nula[i] + (b[i] == 0)

memo = [-1 for i in range(n + 1)]
def dp(i):
    if memo[i] != -1:
        return memo[i]
    if i == n:
        memo[i] = 0
        return 0
    best = dp(i + 1) + (b[i] == 1)
    for r in op[i]:
        best = min(best, dp(r) + nula[r] - nula[i])
    memo[i] = best
    return best

print(dp(0))

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc085/tasks/arc085_d

dp[i][x] = indexがxになるまでは1が連続する際の最小スコア

何もない場合
i <= x では1を選ばなくてはいけない　bが1の時0 bが0の時1
i > x では0を選ばなくてはいけない   bが0の時0 1の時1

i == lがある場合
dp[i][r] = min(dp[i-1][t] + l番目で1を選んだ際のスコア)
           t<r
つまり、区間加算と全体最小値がわかればいい
→遅延評価セグメント木…

"""

#遅延評価セグメント木(tree&lazy)を作る。初期値lisを渡す
#defaultで初期化する

def make_LST(lis,default = float("inf")):

    n = 1
    while n < len(lis):
        n *= 2

    tree = [default] * (2*n-1)
    lazy = [0] * (2*n-1)

    for i in range(len(lis)):
        tree[i+n-1] = lis[i]
    for i in range(n-2,-1,-1):
        tree[i] = min(tree[i*2+1] , tree[i*2+2])

    return tree,lazy

def eval_LST(k,l,r,tree,lazy):
    if lazy[k] != 0:
        tree[k] += lazy[k]

    if r-l > 1:
        lazy[2*k+1] += lazy[k]
        lazy[2*k+2] += lazy[k]

    lazy[k] = 0

#add x to [a,b)
def add_LST(a,b,x,tree,lazy,k=0,l=0,r=-1):

    if r < 0:
        n = (len(tree)+1)//2
        r = n

    eval_LST(k,l,r,tree,lazy)

    if b <= l or r <= a:
        return

    if a <= l and r <= b:
        lazy[k] += x
        eval_LST(k,l,r,tree,lazy)
    else:
        add_LST(a,b,x,tree,lazy,2*k+1,l,(l+r)//2)
        add_LST(a,b,x,tree,lazy,2*k+2,(l+r)//2,r)
        tree[k] = min(tree[2*k+1] , tree[2*k+2])

#range_minimum_query(def)
def rmq_LST(a,b,tree,lazy,k=0,l=0,r=-1):
    if r < 0:
        n = (len(tree)+1)//2
        r = n
    if b <= l or r <= a:
        return float("inf")

    eval_LST(k,l,r,tree,lazy)
    if a <= l and r <= b:
        return tree[k]

    vl = rmq_LST(a,b,tree,lazy,2*k+1,l,(l+r)//2)
    vr = rmq_LST(a,b,tree,lazy,2*k+2,(l+r)//2,r)

    return min(vl,vr)

def getfrom_index_LST(index,tree,lazy):
    return rmq_LST(index,index+1,tree,lazy)

def upd_point_LST(index,newnum,tree,lazy):
    oldnum = getfrom_index_LST(index,tree,lazy)
    difference = newnum - oldnum
    add_LST(index,index+1,difference,tree,lazy)


from sys import stdin

N = int(stdin.readline())
b = list(map(int,stdin.readline().split()))
Q = int(stdin.readline())

rlis = [ [] for i in range(N+1) ]
for i in range(Q):

    l,r = map(int,stdin.readline().split())
    rlis[l].append(r)

tmp = [10**9]*(N+1)
tmp[0] = 0
tree,lazy = make_LST(tmp,10**9)

for i in range(1,N+1):

    #print (tree,lazy)

    #i <= x では1を選ばなくてはいけない　bが1の時0 bが0の時1
    #i > x では0を選ばなくてはいけない   bが0の時0 1の時1

    for r in rlis[i]:
        newnum = rmq_LST(0,r,tree,lazy)

        oldnum = getfrom_index_LST(r,tree,lazy)
        if newnum < oldnum:
            upd_point_LST(r,newnum,tree,lazy)
    
    if b[i-1] == 0:
        add_LST(i,N+1,1,tree,lazy)
    else:
        add_LST(0,i,1,tree,lazy)

#print (tree,lazy)
print (rmq_LST(0,N+1,tree,lazy))

"""
#verify
n,q = map(int,stdin.readline().split())

tree,lazy = make_LST([0]*n,0)

for i in range(q):
    SS = stdin.readline()
    if SS[0] == "0":
        tmp,s,t,x = map(int,SS.split())
        add_LST(s-1,t,x,tree,lazy)
    else:
        tmp,s,t = map(int,SS.split())
        print ( rsq_LST(s-1,t,tree,lazy) )

"""

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

def main():
    n = int(input())
    bb = LI()
    q = int(input())
    lr = defaultdict(list)
    for _ in range(q):
        l, r = MI()
        lr[l-1].append(r-1)
    # print(lr)
    dp = SegtreeMin(n + 1)
    dp.update(0, 0)
    for i in range(n):
        for r in lr[i]:
            dp.update(r + 1, dp.min(i, r + 2))
        case0 = dp.element(i) + bb[i] * 2 - 1
        if case0 < dp.element(i + 1): dp.update(i + 1, case0)
    print(bb.count(0) + dp.element(n))

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class SegtreeMin():
    def __init__(self, n):
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [self.inf] * (tree_width * 2 - 1)

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = min(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最小値
    def min(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return self.inf
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.min(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.min(l, r, seg_i * 2 + 2, segM, segR)
        return min(ret0, ret1)

def main():
    n = int(input())
    bb = LI()
    q = int(input())
    lr = defaultdict(list)
    for _ in range(q):
        l, r = map(int1, input().split())
        lr[l].append(r)
    # print(lr)
    dp = SegtreeMin(n + 1)
    dp.update(0, 0)
    for i in range(n):
        for r in lr[i]:
            dp.update(r + 1, dp.min(i, r + 2))
        dp.update(i + 1, min(dp.element(i + 1), dp.element(i) + bb[i] * 2 - 1))
    print(bb.count(0) + dp.element(n))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
B = list(map(int,readline().split()))
Q = int(readline())
m = map(int,read().split())
LR = sorted(zip(m,m))

class MaxSegTree():
    def __init__(self,N):
        self.Nelem = N
        self.size = 1<<(N.bit_length()) # 葉の要素数
        INF = float('inf')
        self.data = [-INF] * (2*self.size)
        
    def build(self,raw_data):
        # raw_data は 0-indexed
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
            i >>= 1
    
    def get_data(self,i):
        return self.data[i+self.size]

    def get_max(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = -float('inf')
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

"""
・ある場所まで確定して、そこから先を全て1で埋めた場合
・ある場所まで確定して、そこから先を全て0で埋めた場合
の加算スコア
"""
add0 = [0] * (N+1)
add1 = [0] * (N+1)
x = sum(B)
add1[0] = x
add0[0] = N-x
for i,x in enumerate(B,1):
    if x == 0:
        add0[i]=add0[i-1]-1; add1[i] = add1[i-1]
    else:
        add1[i]=add1[i-1]-1; add0[i] = add0[i-1]

"""
ある場所を右端としてとった時点での
・残りをすべて0で埋めたときのスコア
・残りをすべて1で埋めたときのスコア
dp0, dp1 をseg木で管理
"""

dp0 = MaxSegTree(N+1)
dp0.build([add0[0]] + [-float('inf')] * N)
dp1 = MaxSegTree(N+1)
dp1.build([add1[0]] + [-float('inf')] * N)

for L,R in LR:
    # dp1[R] を計算したい。[L,inf) が1で埋まったときのスコア
    x = dp1.get_data(R)
    y = dp0.get_max(0,L-1) + add1[L-1] - add0[L-1] # 0埋め部分を1埋めに修正してdp1[R]に遷移
    z = dp1.get_max(L,R-1) # そのままdp1[R]に遷移
    if y < z: y = z
    if x < y:
        dp1.update(R,y)
        dp0.update(R,y - add1[R] + add0[R])

# 一致を数えていたので、距離に修正
answer = N - dp0.data[1]
print(answer)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

MAX_N = 262144;
INT_MAX = 10 ** 10;


class SegTree:

    def __init__(self):
        self.n = MAX_N
        self.dat = [INT_MAX] * (MAX_N * 2)


    def update(self, i, x):
        i += self.n - 1
        self.dat[i] = x
        while 0 < i:
            i = (i - 1) // 2
            self.dat[i] = min(self.dat[i * 2 + 1], self.dat[i * 2 + 2])


    def query(self, a, b, k = 0, l = 0, r = MAX_N):
        if r <= a or b <= l:
            return INT_MAX
        if a <= l and r <= b:
            return self.dat[k]
        else:
            vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
            vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
            return min(vl, vr)

N = 0
Q = 0
L = [None] * 202020
B = None


def solve():
    seg = SegTree()

    d = 0
    for i in range(N):
        if L[i] is not None:
            for r in L[i]:
                seg.update(r, min(d, seg.query(r, r + 1)))
        d = min(d + (1 if B[i] else -1), seg.query(i, i + 1))


    return d + B.count(0)


def main():
    global N, Q
    global B, L

    N = int(input())
    B = list(map(int, input().split()))
    Q = int(input())
    for i in range(Q):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        if L[l] is None:
            L[l] = []
        L[l].append(r)


    print(solve())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

n=int(input())
b=list(map(int,input().split()))
ope=[[] for i in range(n)]
Q=int(input())
for i in range(Q):
    l,r=map(int,input().split())
    ope[r-1].append(l-1)

res=b.count(0)

Data=[(-1)**((b[i]==1)+1) for i in range(n)]
for i in range(1,n):
    Data[i]+=Data[i-1]
Data=[0]+Data

for i in range(n):
    ope[i].sort(reverse=True)

# N: 処理する区間の長さ
N=n+1
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-2**31, -2**31)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            if data[R-1]:
                data[R-1] = max(v,data[R-1])
            else:
                data[R-1]=v

        if L & 1:
            if data[L-1]:
                data[L-1] = max(v,data[L-1])
            else:
                data[L-1]=v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

for i in range(n+1):
    update(i,i+1,(-Data[i],-Data[i]))
if ope[0]:
    update(1,2,(0,0))

for i in range(1,n):
    val=query(i)
    update(i+1,i+2,(val+Data[i]-Data[i+1],val+Data[i]-Data[i+1]))
    for l in ope[i]:
        val=query(l)
        update(l+1,i+2,(val,val))



print(n-(res+query(n)+Data[n]))

Submission status: Accepted

Solution code:
n=int(input())
b=list(map(int,input().split()))
ope=[[] for i in range(n)]
Q=int(input())
for i in range(Q):
    l,r=map(int,input().split())
    ope[r-1].append(l-1)

res=b.count(0)

Data=[(-1)**((b[i]==1)+1) for i in range(n)]
for i in range(1,n):
    Data[i]+=Data[i-1]
Data=[0]+Data

for i in range(n):
    ope[i].sort(reverse=True)

# N: 処理する区間の長さ
N=n+1
N0 = 2**(N-1).bit_length()
data = [None]*(2*N0)
INF = (-2**31, -2**31)
# 区間[l, r+1)の値をvに書き換える
# vは(t, value)という値にする (新しい値ほどtは大きくなる)
def update(l, r, v):
    L = l + N0; R = r + N0
    while L < R:
        if R & 1:
            R -= 1
            if data[R-1]:
                data[R-1] = max(v,data[R-1])
            else:
                data[R-1]=v

        if L & 1:
            if data[L-1]:
                data[L-1] = max(v,data[L-1])
            else:
                data[L-1]=v
            L += 1
        L >>= 1; R >>= 1
# a_iの現在の値を取得
def _query(k):
    k += N0-1
    s = INF
    while k >= 0:
        if data[k]:
            s = max(s, data[k])
        k = (k - 1) // 2
    return s
# これを呼び出す
def query(k):
    return _query(k)[1]

for i in range(n+1):
    update(i,i+1,(-Data[i],-Data[i]))
if ope[0]:
    update(1,2,(0,0))

for i in range(1,n):
    val=query(i)
    update(i+1,i+2,(val+Data[i]-Data[i+1],val+Data[i]-Data[i+1]))
    for l in ope[i]:
        val=query(l)
        update(l+1,i+2,(val,val))



print(n-(res+query(n)+Data[n]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
B = list(map(int,readline().split()))
Q = int(readline())
m = map(int,read().split())
LR = sorted(zip(m,m))

class MaxSegTree():
    def __init__(self,raw_data):
        N = len(raw_data)
        self.size = 1<<(N.bit_length()) # 葉の要素数
        self.data = [0] * (2*self.size)
        self.build(raw_data)
        
    def build(self,raw_data):
        for i,x in enumerate(raw_data):
            self.data[self.size+i] = x
        for i in range(self.size-1,0,-1):
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
    
    def update(self,i,x):
        i += self.size
        self.data[i] = x
        i >>= 1
        while i:
            x = self.data[i+i]; y = self.data[i+i+1]
            self.data[i] = x if x>y else y
            i >>= 1
    
    def get_data(self,i):
        return self.data[i+self.size]

    def get_max(self,L,R):
        # [L,R] に対する値を返す
        L += self.size
        R += self.size + 1
        # [L,R) に変更
        x = 0
        while L < R:
            if L&1:
                y = self.data[L]
                if x < y: x = y
                L += 1
                
            if R&1:
                R -= 1
                y = self.data[R]
                if x < y: x = y
            L >>= 1; R >>= 1
        return x

"""
・あるから先を全て0で埋めた場合
・あるから先を全て1で埋めた場合
"""
add1 = [0] * (N+1)
add1[0] = sum(B)
for i,x in enumerate(B,1):
    if x:
        add1[i] = add1[i-1] - 1
    else:
        add1[i] = add1[i-1]
add0 = [N - i - x for i,x in enumerate(add1)]

add0,add1

# ある場所を最後の右端まで使ったとする。残りを全て 0 / 1 で埋めたときのスコア
dp0 = MaxSegTree([0] * (N+1))
dp1 = MaxSegTree([0] * (N+1))
dp0.update(0,add0[0])
dp1.update(0,add1[0])

for L,R in LR:
    a = dp1.get_data(R)
    b = dp0.get_max(0,L-1) + add1[L-1] - add0[L-1]
    c = dp1.get_max(L,R-1)
    if b < c:
        b = c
    if a < b:
        dp1.update(R, b)
        dp0.update(R, b - add1[R] + add0[R])

answer = N - dp0.get_max(0,N)
print(answer)