Problem:

イルミネーション (Illumination)

問題文

JOI 氏は，自宅の敷地に N 本の木を所有している．これらの木は一列に並んでおり，順に 1 から N までの整数で番号が付けられている．

この冬，JOI 氏はいくつかの木を選んで，イルミネーションを飾り付けることにした．イルミネーションには美しさと呼ばれる値が定まっている．木 i にイルミネーションを飾り付ける場合の美しさは A_i である．

JOI 氏は，あまりに近い 2 つの木の両方にイルミネーションを飾り付けてしまうと，眩しすぎる場合があることに気がついた．具体的には，j = 1, 2, ..., M に対して，木 L_j, L_j + 1, ..., R_j のうち 2 つ以上にイルミネーションを飾り付けるべきではないということが判明した．

この条件に従ってイルミネーションを飾り付けるときの，美しさの合計の最大値を求めよ．

制約

1 ≦ N ≦ 200000 (= 2×10^5)

1 ≦ M ≦ 200000 (= 2×10^5)

1 ≦ A_i ≦ 1000000000 (= 10^9) (1 ≦ i ≦ N)

1 ≦ L_j ≦ R_j ≦ N (1 ≦ j ≦ M)

入力・出力

入力

入力は以下の形式で標準入力から与えられる．

N M

A_1 A_2 ... A_N

L_1 R_1

L_2 R_2

⋮

L_M R_M

出力

イルミネーションの美しさの合計の最大値を 1 行で出力せよ．

10 点) N ≦ 16，M ≦ 16

(30 点) N ≦ 300，M ≦ 300

(30 点) N ≦ 4000，M ≦ 4000

(30 点) 追加の制限はない．

-->

入出力例

入力例 1

4 1
1 2 3 8
2 4

出力例 1

9

この入力例では，木 1, 4 にイルミネーションを飾り付けると，美しさの合計が 9 となり最大となる．L_1 = 2, R_1 = 4 なので，木 2, 3, 4 のうち 2 つ以上にイルミネーションを飾り付けることはできない．例えば木 1, 2, 4 にイルミネーションを飾り付けることはできないことに注意せよ．

入力例 2

5 2
2 3 9 5 6
1 3
2 4

出力例 2

15

入力例 3

20 10
870851814 594414687 615919461 65033245 460143082 617460823 881870957 126041265 623075703 34130727 27054628 853567651 483228744 491145755 220689940 148007930 229257101 790404982 612186806 281076231
15 19
20 20
12 13
1 4
19 19
9 13
3 6
9 12
16 16
18 19

出力例 3

4912419478

情報オリンピック日本委員会作 『第 18 回日本情報オリンピック JOI 2018/2019 予選競技課題』



Sample input:
4 1
1 2 3 8
2 4


Sample output:
9

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
*A, = map(int, input().split())
S = [[] for i in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    S[l-1].append(r)

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

update(0, 0)
que = deque()
for i in range(N):
    while que and que[0][1] <= i:
        que.popleft()

    r = (que[0][0] if que else i)+1
    v = query(0, r) + A[i]
    update(i+1, v)

    for r in S[i]:
        que.append((i, r))
print(query(0, N+1))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import array
from fractions import Fraction
import functools
import itertools
import math
import os
import sys


def main():
    N, M = read_ints()
    A = read_ints()
    B = [(l, r) for l, r in [read_ints() for _ in range(M)]]
    print(solve(N, M, A, B))


def solve(N, M, A, B):
    B.sort()
    bi = 0
    dp = [0] * (N + 1)
    range_counts = []
    range_starts = []
    ri = 0
    range_map = {}
    end_map = {}
    for i in range(1, N + 1):
        while bi < len(B) and B[bi][0] == i:
            l, r = B[bi]
            if l not in range_map:
                range_map[l] = len(range_counts)
                range_counts.append(0)
                range_starts.append(l)
            range_counts[range_map[l]] += 1
            if r not in end_map:
                end_map[r] = []
            end_map[r].append(range_map[l])
            bi += 1

        li = i - 1
        if ri < len(range_counts):
            li = range_starts[ri] - 1
        dp[i] = max(dp[i - 1], dp[li] + A[i - 1])

        if i in end_map:
            for rangei in end_map[i]:
                range_counts[rangei] -= 1
        while ri < len(range_counts) and range_counts[ri] == 0:
            ri += 1

    return dp[-1]


###############################################################################
# AUXILIARY FUNCTIONS

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    A=LI()
    LR = []
    for _ in range(M):
        l,r = MI_()
        LR.append((l,r))
    LR.sort()
    NG_left = [i for i in range(N)]
    index = 0
    for l,r in LR:
        for i in range(max(index, l), r+1):
            NG_left[i] = l
            index = i+1
    # print(NG_left)
    dp = [0]*N #dp[i]:= i番目までの木で実現できる明るさ
    dp[0] = A[0]
    for i in range(1,N):
        if NG_left[i]==0:
            dp[i] = max(dp[i-1], A[i])
        else:
            dp[i] = max(dp[i-1], A[i] + dp[NG_left[i]-1])
    print(dp[-1])

if __name__ == '__main__':
    main()



"""##GREEDY check -> NG
N,M=MI()
A=LI()
LR = []
for _ in range(M):
    l,r = MI_()
    LR.append((l,r))
ng = set()
B=[(a,i) for i,a in enumerate(A)]
B.sort(reverse=True)
ans = 0
for a,i in B:
    if i in ng:
        continue
    for l,r in LR:
        for j in range(l,r+1):
            ng.add(j)
    ans+=a
print(ans)"""

Submission status: Accepted

Solution code:
# siawaseegoisuto273さんのものを参考にした。(pythonで書いた)
#

# N, Mの数
N, M = map(int, input().split())
L = [0] * M
R = [0] * M

# 明るさ
A = list(map(int, input().split()))


# 制約条件
for i in range(M):
    L[i], R[i] = map(int, input().split())
    
pre = [0] * (N+1)
dp = [0] * (N+1)

# 制約条件の書き換え
# pre[i]は、位置iが含まない制約の番号の最大を表す(ただしiより小さい)
# pre[i]が0は、同一の制約の中にi=1が含まれることを表す。
# preの作成のアルゴリズムが一番むずかしい
#
# 1. 
# R[i]の値を配列の位置情報(何番目)で表現する。
# pre[R[i]]は、L[i]の情報を表す(正確にはL[i]-1)
# ※制約条件は広い方に吸収される
# (R[i], L[i]) = {(4, 5), (3, 5), (6, 9), (7, 8), (10, 11), (10, 13)}
#              ->{(3, 5), (6, 9), 10, 13} となる。
#
# 2. 条件の隅の情報しか更新していないため、最後に後ろから値を詰めていって、完成する。
# 


# 制約の初期化
for i in range(1, N+1):
    pre[i] = i - 1

# 制約条件に含まれない左側
for i in range(M):
    pre[R[i]] = min(pre[R[i]], L[i]-1)
    # print("print pre")
    # print(pre)
    # print("")
    
for i in range(N-1, 0, -1):
    pre[i] = min(pre[i], pre[i+1])
    # print("print pre2")
    # print(pre)
    # print("")

# 動的計画法を解いていく
# 小さい方から値を詰めていく
for i in range(1, N+1):
    dp[i]=max(dp[i-1], dp[pre[i]] + A[i-1])
    # print(dp)

print(dp[N])