Problem:


Score : 900 points

Problem Statement

There is a string S of length N consisting of characters 0 and 1. You will perform the following operation for each i = 1, 2, ..., m:

Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.

Here, the sequence l_i is non-decreasing.

How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?

Constraints

2≦N≦3000

1≦M≦3000

S consists of characters 0 and 1.

The length of S equals N.

1≦l_i < r_i≦N

l_i ≦ l_{i+1}

Input

The input is given from Standard Input in the following format:

N M
S
l_1 r_1
:
l_M r_M

Output

Print the number of the possible values for S after the M operations, modulo 1000000007.

Sample Input 1

5 2
01001
2 4
3 5

Sample Output 1

6

After the first operation, S can be one of the following three: 01001, 00101 and 00011.

After the second operation, S can be one of the following six: 01100, 01010, 01001, 00011, 00101 and 00110.

Sample Input 2

9 3
110111110
1 4
4 6
6 9

Sample Output 2

26

Sample Input 3

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

Sample Output 3

143



Sample input:
5 2
01001
2 4
3 5


Sample output:
6

Submission status: Wrong Answer

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

n,m = map(int,readline().split())
s = input()
mp = map(int,read().split())

r = [0]*n
for i,j in zip(mp,mp):
    if r[i-1] < j-1:
        r[i-1] = j-1

for i in range(1,n):
    if r[i] < r[i-1]: r[i] = r[i-1]

zero = [0]*n
for i in range(n):
    zero[i] = zero[i-1]
    if s[i]=="0": zero[i] += 1

#print(r)
#print(s)
#print(zero)

MOD = 10**9+7
dp = [0]*n
dp[0] = 1
for i in range(n):
    L = max(zero[r[i]] + i - r[i],0)
    R = min(zero[r[i]],i+1)
    ndp = [0]*n

    for i in range(L,R+1):
        if i: ndp[i] += dp[i-1]
        ndp[i] += dp[i]
        ndp[i] %= MOD        
    dp = ndp


    #print(L,R,r[i],zero[r[i]],dp)
print(sum(dp)%MOD)

Submission status: Wrong Answer

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


M = 10 ** 9 + 7


def solve(n, m, s, lst):

    cnt = [0] * n
    t = 0
    for i in range(n):
        if s[i] == '1':
            t += 1
        cnt[i] = t


    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = 0
    j = 0
    for i in range(n):
        while j < m:
            lj, rj = lst[j]
            if lj <= i:
                r = max(r, rj)
                j += 1
            else:
                break
        if r <= i:
            c = cnt[i]
            if 0 < c:
                dp[i + 1][cnt[i]] = dp[i][c] + dp[i][c - 1]
            else:
                dp[i + 1][0] = dp[i][0]
        else:
            for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                if 0 < k:
                    dp[i + 1][k] = dp[i][k] + dp[i][k - 1]
                else:
                    dp[i + 1][0] = dp[i][0]

    return dp[n][cnt[n - 1]]


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    lst = []
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        lst.append((l, r))

    print(solve(n, m, s, lst))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


M = 10 ** 9 + 7

def solve(n, m, s, p):

    cnt = [0] * (n + 1)
    c = 0
    for i in range(n):
        cnt[i] = c
        if s[i] == '1':
            c += 1
    cnt[n] = c


    ans = 1
    for sp in p:
        dp = [[0] * (n + 2) for _ in range(n + 2)]
        l0, r0 = sp[0]
        c0 = cnt[l0]
        dp[1][1] = 1
        t0 = 0
        t1 = 0
        r = r0
        for tpl in sp:
            nl, nr = tpl
            nr = max(r, nr)
            nt1 = cnt[nr] - c0
            nt0 = nr - l0 - nt1
            for i in range(max(nl - l0 - t1, 0), t0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(max(nl - l0 - t0, 0), t1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            for i in range(t0 + 1, nt0 + 1):
                for j in range(t1 + 1, nt1 + 1):
                    dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % M
            t0 = nt0
            t1 = nt1
        ans *= dp[t0 + 1][t1 + 1]
        ans %= M

    return ans


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    p = []
    ll = -1
    lr = 0
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r)
        r = max(lr, r)
        if l == ll:
            sp.pop()
            sp.append((l, r))
        else:
            if lr <= l:
                sp = []
                p.append(sp)
            sp.append((l, r))
        ll = l
        lr = r

    print(solve(n, m, s, p))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
mod=10**9+7

N,M=map(int,input().split())
L=-1;R=-1
S=input()
ope=[]
for i in range(M):
    l,r=map(int,input().split())
    l-=1;r-=1
    if L<=l and r<=R:
        continue
    else:
        L,R=l,r
        ope.append((l,r))

M=len(ope)
data=[-1]*N
for i in range(M):
    l,r=ope[i]
    for j in range(l,r+1):
        data[j]=i

dp=[[0 for i in range(N+1)] for j in range(N+1)]

for j in range(N+1):
    dp[-1][j]=1

for i in range(N-1,-1,-1):
    id=data[i]
    if id!=-1:
        l,r=ope[id]
        temp1=sum(int(S[k]) for k in range(r+1))
        temp0=r+1-temp1
        for j in range(temp1+1):
            np1=temp1-j
            np0=temp0-(i-j)
            if np1==0:
                if np0>0:
                    dp[i][j]=dp[i+1][j]
            else:
                if np0>0:
                    dp[i][j]=(dp[i+1][j+1]+dp[i+1][j])%mod
                elif np0==0:
                    dp[i][j]=dp[i+1][j+1]
    else:
        if S[i]=="1":
            for j in range(N):
                dp[i][j]=dp[i+1][j+1]
        else:
            for j in range(N+1):
                dp[i][j]=dp[i+1][j]

print(dp[0][0])

Submission status: Accepted

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

n,m = map(int,readline().split())
s = input()
mp = map(int,read().split())

r = list(range(n))
for i,j in zip(mp,mp):
    if r[i-1] < j-1:
        r[i-1] = j-1

for i in range(1,n):
    if r[i] < r[i-1]: r[i] = r[i-1]

zero = [0]*n
one = [0]*n
for i in range(n):
    zero[i] = zero[i-1]
    one[i] = one[i-1]
    if s[i]=="0": zero[i] += 1
    else: one[i] += 1


#print(r)
#print(s)
#print(zero)

MOD = 10**9+7
dp = [0]*n
dp[0] = 1
for i in range(n):
    L = max(zero[r[i]] + i - r[i],0)
    R = min(zero[r[i]],i+1)
    ndp = [0]*n

    for i in range(L,R+1):
        if i: ndp[i] += dp[i-1]
        ndp[i] += dp[i]
        ndp[i] %= MOD        
    dp = ndp


    #print(L,R,r[i],zero[r[i]],dp)
print(sum(dp))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/arc065/tasks/arc065_d

圧倒的dp感

lは非減少なので、 l[i-1] ～l[i] の間が確定する範囲

dp[i][今の区間に残っている1の数] = 並び替えの通り数　でやると
dp推移がO(N^2)になってしまう…

1の位置さえ決まればよい。
あらかじめ、それぞれの1に関して、移動しうる最小のindexと最大のindexを前計算
→どうやって？
→heapといもす法で、最小・最大値管理しつつ

あとはdp中に一点取得、区間加算がO(N)で出来れば、O(N**2)で解ける
→dp[i個目までの1を処理][右端にある1のindex]
とし、最後に累積和で区間加算する→DP推移はO(N)なのでおｋ

→なんか違う？
→1をもってける範囲の右端が実際より短くなっているのが原因


"""
from collections import deque
import heapq
N,M = map(int,input().split())
S = input()
"""
lri = deque([])
rpick = [ [] for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    lri.append([l-1,r-1,i])
    rpick[r].append(i)

lheap = []
rheap = []
state = [False] * M

LRlis = []

for i in range(N):

    while len(lri) > 0 and lri[0][0] == i: #新たに区間を入れる
        l,r,ind = lri.popleft()
        heapq.heappush(lheap,[l,ind])
        heapq.heappush(rheap,[-1*r,ind])

    for pickind in rpick[i]:

        state[pickind] = True

    while len(lheap) > 0 and state[ lheap[0][1] ]:
        heapq.heappop(lheap)
    while len(rheap) > 0 and state[ rheap[0][1] ]:
        heapq.heappop(rheap)

    if S[i] == "1":

        if len(lheap) == 0 or len(rheap) == 0:
            LRlis.append([i,i])
        else:
            LRlis.append([lheap[0][0] , -1 * rheap[0][0] ])

"""
lri = []
for i in range(M):
    l,r = map(int,input().split())
    lri.append([l-1,r-1,i])
lri.append([N,float("inf"),float("inf")])

nexvisit = 0
onenum = 0
LRlis = []
LRlisind = 0
r = 0
for loop in range(M):
    
    l,nr,tempi = lri[loop]
    r = max(nr,r)
    nexl = lri[loop+1][0]
    #print (l,r,nexl)

    for i in range( max(l,nexvisit) , r+1 ):
        if S[i] == "1":
            LRlis.append([l,None])
            onenum += 1
            nexvisit = max(nexvisit,i+1)
    if r-nexl+1 < onenum:

        for i in range(min(onenum , onenum - (r-nexl+1))):
            LRlis[LRlisind][1] = r-onenum+1
            onenum -= 1
            LRlisind += 1
            
mod = 10**9+7
dp = [0] * (N+1)
#print (LRlis)

for i in range(len(LRlis)):

    #print (dp)

    l,r = LRlis[i]

    ndp = [0] * (N+1)

    if i == 0:
        ndp[l] += 1
        ndp[r+1] -= 1
    else:

        for v in range(r):

            ndp[max(l,v+1)] += dp[v]
            ndp[r+1] -= dp[v]

    for j in range(N):
        ndp[j+1] += ndp[j]
        ndp[j] %= mod
        ndp[j+1] % mod

    dp = ndp

#print (dp)
print (sum(dp[0:N]) % mod)

Submission status: Accepted

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

MOD = 10**9+7
N, M = map(int, readline().split())
S = list(map(int, readline().strip()))
Query = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(M)]

PP = S.count(1)

Li = [None]*PP
Ri = [None]*PP

T1 = S[:]
for l, r in Query:
    cnt = 0
    for i in range(l, r+1):
        cnt += T1[i]
    for i in range(l, l+cnt):
        T1[i] = 1
    for i in range(l+cnt, r+1):
        T1[i] = 0
T2 = S[:]
for l, r in Query:
    cnt = 0
    for i in range(l, r+1):
        cnt += 1 - T2[i]
    for i in range(l, l+cnt):
        T2[i] = 0
    for i in range(l+cnt, r+1):
        T2[i] = 1

cnt = 0
for i in range(N):
    if T1[i]:
        Li[cnt] = i
        cnt += 1
cnt = 0
for i in range(N):
    if T2[i]:
        Ri[cnt] = i+1
        cnt += 1

dp = [0]*N
for i in range(Li[0], Ri[0]):
    dp[i] = 1

for j in range(1, PP):
    dp2 = [0] + dp[:-1]
    for i in range(1, N):
        dp2[i] = (dp2[i]+dp2[i-1])%MOD
    for i in range(Li[j]):
        dp2[i] = 0
    for i in range(Ri[j], N):
        dp2[i] = 0
    dp = dp2[:]
res = 0
for d in dp:
    res = (res+d)%MOD
print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import numpy as np

MOD = 10**9 + 7

N,M = map(int,input().split())
S = np.array(list(input().rstrip()),dtype='U1')
LR = [[int(x) for x in input().split()] for _ in range(M)]

cnt_0 = (S=='0').cumsum()
cnt_1 = (S=='1').cumsum()
canuse_0 = cnt_0
canuse_1 = cnt_1
for L,R in LR:
    canuse_0[L-1] = max(canuse_0[L-1],cnt_0[R-1])
    canuse_1[L-1] = max(canuse_1[L-1],cnt_1[R-1])
np.maximum.accumulate(canuse_0,out=canuse_0)
np.maximum.accumulate(canuse_1,out=canuse_1)

# 1を使った個数で
dp = np.zeros(N+1,dtype=np.int64)
dp[0] = 1
for i in range(N):
    prev = dp
    dp = np.zeros(N+1,dtype=np.int64)
    # i番目を置いた後で、1の個数の範囲
    left = max(0,(i+1)-canuse_0[i])
    right = canuse_1[i]
    # 0を使う
    dp[left:right+1] += prev[left:right+1]
    # 1を使う
    left = max(1,left)
    dp[left:right+1] += prev[left-1:right]
    dp %= MOD

answer = dp.sum()
print(answer)

Submission status: Accepted

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


M = 10 ** 9 + 7


def solve(n, m, s, lst):

    cnt = [0] * n
    t = 0
    for i in range(n):
        if s[i] == '1':
            t += 1
        cnt[i] = t


    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    r = 0
    j = 0
    for i in range(n):
        while j < m:
            lj, rj = lst[j]
            if lj <= i:
                r = max(r, rj)
                j += 1
            else:
                break
        if r <= i:
            c = cnt[i]
            if 0 < c:
                dp[i + 1][cnt[i]] = (dp[i][c] + dp[i][c - 1]) % M
            else:
                dp[i + 1][0] = dp[i][0]
        else:
            for k in range(max(0, cnt[r] - r + i), min(i + 1, cnt[r]) + 1):
                if 0 < k:
                    dp[i + 1][k] = (dp[i][k] + dp[i][k - 1]) % M
                else:
                    dp[i + 1][0] = dp[i][0]

    return dp[n][cnt[n - 1]]


def main():
    n, m = input().split()
    n = int(n)
    m = int(m)
    s = input()
    lst = []
    for _ in range(m):
        l, r = input().split()
        l = int(l) - 1
        r = int(r) - 1
        lst.append((l, r))

    print(solve(n, m, s, lst))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
 
typedef long long ll;
const int MOD = (int)1e9 + 7;
int add(int x, int y)
{
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
int sub(int x, int y)
{
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
int mult(int x, int y)
{
	return ((ll)x * y) % MOD;
}
 
const int N = 3030;
int n;
char s[N];
int a[N];
int b[N];
int dp[N][N];
int C[N][N];
 
void read()
{
	int m;
	scanf("%d%d", &n, &m);
	scanf(" %s ", s);
	for (int i = 0; i < n; i++)
		a[i] = (int)(s[i] - '0');
	for (int i = 0; i < n; i++)
		b[i] = i + 1;
	while(m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		l--;
		b[l] = max(b[l], r);
	}
	for (int i = 1; i < n; i++)
		b[i] = max(b[i], b[i - 1]);
}
 
int main()
{
	read();
 
	for (int i = 0; i < N; i++)
		C[i][0] = C[i][i] = 1;
	for (int i = 1; i < N; i++)
		for (int j = 1; j < i; j++)
			C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
	
	dp[0][0] = 1;
	int cur = 0;
	for (int i = 0; i < n; i++)
	{
		int willAdd = 0;
		while(cur < b[i])
		{
			willAdd += a[cur];
			cur++;
		}
		for (int x = 0; x <= n; x++)
		{
			if (dp[i][x] == 0) continue;
			int y = x + willAdd;
			if (y != 0)
				dp[i + 1][y - 1] = add(dp[i + 1][y - 1], dp[i][x]);
			if (y != cur - i)
				dp[i + 1][y] = add(dp[i + 1][y], dp[i][x]);
		}
	}
	printf("%d\n", dp[n][0]);
 
	return 0;
}

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
        self.size = [1] * (n+1)
    
    # 譬ｹ繧呈､懃ｴ｢縺吶ｋ髢｢謨ｰ
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.find(self.par[x])
  
    # 邨仙粋(unite)縺吶ｋ髢｢謨ｰ
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    # 蜷後§繧ｰ繝ｫ繝ｼ繝励↓螻槭☆繧九°繧貞愛螳壹☆繧矩未謨ｰ
    def same_check(self, x, y):
        return self.find(x) == self.find(y)
    
    # 隕∫ｴ縺悟ｱ槭☆繧区惠縺ｮ豺ｱ縺輔ｒ霑斐☆髢｢謨ｰ
    def get_depth(self, x):
        return self.rank[self.find(x)]
    
    # 隕∫ｴ縺悟ｱ槭☆繧区惠縺ｮ繧ｵ繧､繧ｺ繧定ｿ斐☆髢｢謨ｰ
    def get_size(self, x):
        return self.size[self.find(x)]
    
    # 繧ｰ繝ｫ繝ｼ繝玲焚繧定ｿ斐☆髢｢謨ｰ
    def group_sum(self):
        c = 0
        for i in range(len(self.par)):
            if self.find(i) == i:
                c += 1
        return c

if __name__ == "__main__":
    N,K,L = map(int, input().split())
    uf = UnionFind(N)

    for i in range(K):
        p, q = [int(i) for i in input().split()]
        uf.unite(p, q)
    
    ans = [1]*N
    for i in range(L):
        r, s = [int(i) for i in input().split()]
        if uf.same_check(r, s):
            ans[r-1] += 1
            ans[s-1] += 1
    
    print(*ans)