Strange Function (Codeforces 1334F)
Tags: Greedy, binary search

Let's denote the following function $$$f$$$. This function takes an array $$$a$$$ of length $$$n$$$ and returns an array. Initially the result is an empty array. For each integer $$$i$$$ from $$$1$$$ to $$$n$$$ we add element $$$a_i$$$ to the end of the resulting array if it is greater than all previous elements (more formally, if $$$a_i > \max\limits_{1 \le j < i}a_j$$$). Some examples of the function $$$f$$$:  if $$$a = [3, 1, 2, 7, 7, 3, 6, 7, 8]$$$ then $$$f(a) = [3, 7, 8]$$$;  if $$$a = [1]$$$ then $$$f(a) = [1]$$$;  if $$$a = [4, 1, 1, 2, 3]$$$ then $$$f(a) = [4]$$$;  if $$$a = [1, 3, 1, 2, 6, 8, 7, 7, 4, 11, 10]$$$ then $$$f(a) = [1, 3, 6, 8, 11]$$$. You are given two arrays: array $$$a_1, a_2, \dots , a_n$$$ and array $$$b_1, b_2, \dots , b_m$$$. You can delete some elements of array $$$a$$$ (possibly zero). To delete the element $$$a_i$$$, you have to pay $$$p_i$$$ coins (the value of $$$p_i$$$ can be negative, then you get $$$|p_i|$$$ coins, if you delete this element). Calculate the minimum number of coins (possibly negative) you have to spend for fulfilling equality $$$f(a) = b$$$.

Input: The first line contains one integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^5)$$$ — the length of array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$ — the array $$$a$$$.The third line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ $$$(|p_i| \le 10^9)$$$ — the array $$$p$$$.The fourth line contains one integer $$$m$$$ $$$(1 \le m \le n)$$$ — the length of array $$$b$$$.The fifth line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ $$$(1 \le b_i \le n, b_{i-1} < b_i)$$$ — the array $$$b$$$.

Output: If the answer exists, in the first line print YES. In the second line, print the minimum number of coins you have to spend for fulfilling equality $$$f(a) = b$$$.Otherwise in only line print NO.


Sample Inputs:
11
4 1 3 3 7 8 7 9 10 7 11
3 5 0 -2 5 3 6 7 8 2 4
3
3 7 10

6
2 1 5 3 6 5
3 -9 0 16 22 -14
4
2 3 5 6

Sample Outputs:
YES
20

NO

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
a = [0] + list(map(int, input().split())) + [n + 1]
p = [0] + list(map(int, input().split())) + [0]
m = int(input())
b = [0] + list(map(int, input().split())) + [n + 1]
x = [[] for _ in range(n + 5)]
for i in range(n + 2):
    x[a[i]].append(i)
tree = fenwick_tree(n + 5)
for i in range(n, 0, -1):
    pi = p[i]
    j = i
    while j < len(tree):
        tree[j] += pi
        j += j & -j
ans = 'YES'
for i in b:
    if not x[i]:
        ans = 'NO'
        break
if ans == 'NO':
    print(ans)
    exit()
inf = pow(10, 16) + 1
dp = [inf] * (n + 5)
dp[0] = 0
z = 1
for i in range(m + 1):
    (u, v) = (b[i], b[i + 1])
    (xu, xv) = (x[u], x[v])
    (j, k, l) = (0, 0, -1)
    while j ^ len(xu) or k ^ len(xv):
        if k == len(xv):
            if l == -1 or dp[xu[j]] < dp[l] + get_sum(l + 1, xu[j]):
                l = xu[j]
            j += 1
        elif j == len(xu):
            if l ^ -1:
                dp[xv[k]] = dp[l] + get_sum(l + 1, xv[k] - 1)
            k += 1
        elif xu[j] < xv[k]:
            if l == -1 or dp[xu[j]] < dp[l] + get_sum(l + 1, xu[j]):
                l = xu[j]
            j += 1
        else:
            if l ^ -1:
                dp[xv[k]] = dp[l] + get_sum(l + 1, xv[k] - 1)
            k += 1
    for j in range(z, v + 1):
        for k in x[j]:
            if p[k] > 0:
                add(k, -p[k])
    z = v + 1
c = dp[n + 1]
if c > pow(10, 15):
    ans = 'NO'
print(ans)
if ans == 'YES':
    print(c)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def fenwick_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum0(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum(s, t):
    ans = get_sum0(t) - get_sum0(s - 1)
    return ans

def add(i, x):
    while i < len(tree):
        tree[i] += x
        i += i & -i
n = int(input())
a = [0] + list(map(int, input().split())) + [n + 1]
p = [0] + list(map(int, input().split())) + [0]
m = int(input())
b = [0] + list(map(int, input().split())) + [n + 1]
x = [[] for _ in range(n + 5)]
for i in range(n + 2):
    x[a[i]].append(i)
tree = fenwick_tree(n + 5)
for i in range(n, 0, -1):
    pi = p[i]
    j = i
    while j < len(tree):
        tree[j] += pi
        j += j & -j
ans = 'YES'
for i in b:
    if not x[i]:
        ans = 'NO'
        break
if ans == 'NO':
    print(ans)
    exit()
inf = pow(10, 16) + 1
dp = [inf] * (n + 5)
dp[0] = 0
z = 1
for i in range(m + 1):
    (u, v) = (b[i], b[i + 1])
    (xu, xv) = (x[u], x[v])
    (j, k, l) = (0, 0, -1)
    while j ^ len(xu) or k ^ len(xv):
        if k == len(xv):
            if l == -1 or dp[xu[j]] < dp[l] + get_sum(l + 1, xu[j]):
                l = xu[j]
            j += 1
        elif j == len(xu):
            if l ^ -1:
                dp[xv[k]] = dp[l] + get_sum(l + 1, xv[k] - 1)
            k += 1
        elif xu[j] < xv[k]:
            if l == -1 or dp[xu[j]] < dp[l] + get_sum(l + 1, xu[j]):
                l = xu[j]
            j += 1
        else:
            if l ^ -1:
                dp[xv[k]] = dp[l] + get_sum(l + 1, xv[k] - 1)
            k += 1
    for j in range(z, v + 1):
        for k in x[j]:
            if p[k] > 0:
                add(k, -p[k])
    z = v + 1
c = dp[n + 1]
if c > pow(10, 15):
    ans = 'NO'
print(ans)
if ans == 'YES':
    print(c)

Solution (Python):
from io import BytesIO, IOBase
import sys
import os
import bisect
import math
import random
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase
from typing import *

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return list(input().split())

def LII():
    return list(map(int, input().split()))

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')

class LazySegmentTree:

    def __init__(self, array):
        self.n = len(array)
        self.size = 1 << (self.n - 1).bit_length()
        self.func = min
        self.default = float('inf')
        self.data = [self.default] * (2 * self.size)
        self.lazy = [0] * (2 * self.size)
        self.process(array)

    def process(self, array):
        self.data[self.size:self.size + self.n] = array
        for i in range(self.size - 1, -1, -1):
            self.data[i] = self.func(self.data[2 * i], self.data[2 * i + 1])

    def push(self, index):
        """"""
        self.lazy[2 * index] += self.lazy[index]
        self.lazy[2 * index + 1] += self.lazy[index]
        self.data[2 * index] += self.lazy[index]
        self.data[2 * index + 1] += self.lazy[index]
        self.lazy[index] = 0

    def build(self, index):
        """"""
        index >>= 1
        while index:
            self.data[index] = self.func(self.data[2 * index], self.data[2 * index + 1]) + self.lazy[index]
            index >>= 1

    def query(self, alpha, omega):
        """"""
        res = self.default
        alpha += self.size
        omega += self.size + 1
        for i in reversed(range(1, alpha.bit_length())):
            self.push(alpha >> i)
        for i in reversed(range(1, (omega - 1).bit_length())):
            self.push(omega - 1 >> i)
        while alpha < omega:
            if alpha & 1:
                res = self.func(res, self.data[alpha])
                alpha += 1
            if omega & 1:
                omega -= 1
                res = self.func(res, self.data[omega])
            alpha >>= 1
            omega >>= 1
        return res

    def update(self, alpha, omega, value):
        """"""
        alpha += self.size
        omega += self.size + 1
        (l, r) = (alpha, omega)
        while alpha < omega:
            if alpha & 1:
                self.data[alpha] += value
                self.lazy[alpha] += value
                alpha += 1
            if omega & 1:
                omega -= 1
                self.data[omega] += value
                self.lazy[omega] += value
            alpha >>= 1
            omega >>= 1
        self.build(l)
        self.build(r - 1)
n = II()
nums = LII()
values = LII()
m = II()
to_get = LII()
seg = LazySegmentTree([0] + [10 ** 18] * m)
for (v, p) in zip(nums, values):
    pos = bisect.bisect_left(to_get, v)
    if pos < m and to_get[pos] == v:
        curr_val = seg.query(pos + 1, pos + 1)
        new_val = min(seg.query(pos, pos), curr_val + p)
        if new_val < curr_val:
            seg.update(pos + 1, pos + 1, new_val - curr_val)
        seg.update(0, pos, p)
        if p < 0 and pos + 2 <= m:
            seg.update(pos + 2, m, p)
    else:
        seg.update(0, pos, p)
        if p < 0 and pos + 1 <= m:
            seg.update(pos + 1, m, p)
ans = seg.query(m, m)
if ans >= 10 ** 17:
    print('NO')
else:
    print('YES')
    print(ans)