COCI 2015/2016 contest1 5- 미술품 판매상(RELATIVNOST) > 문제은행 : 정보올림피아드&알고리즘




2980 : 미술품 판매상(RELATIVNOST)

제한시간
4000 ms   
메모리제한
32 MB   
해결횟수
4 회   
시도횟수
49 회   

문제

경원이는 미술품 판매상이다. N명의 단골 고객을 확보하고 있으며 고객들에게 미술품을 판매한다. 

각 고객은 컬러 그림(들)이나 흑백그림(들) 중 한 종류를 구매한다. 두 종류를 한꺼번에 구매 하지는 않는다. 

k번째 고객은 많아야 ak개의 컬러 그림이나 많아야 bk개의 흑백 그림을 구매하기를 원한다.

 

경원이는 각 고객에 대하여 적어도 하나의 그림은 반드시 받을 수 있도록 판매한다. 

또한 거의 무한대의 그림을 보유하고 있어 고객들이 주문하는 개수를 모두 충족시킬 수 있다.

 

경원이는 흑백그림보다는 컬러 그림 판매를 좋아하는 편이다. 그래서 고객들 중에 C명 이상의 고객이 컬러 그림을 구입하기를 원한다.

 

그런데 경원이의 고객들은 지속적으로 희망하는 그림의 주문 개수를 바꾼다. 

그때 마다 경원이는 “적어도 C명 이상의 고객이 컬러그림을 구입하는 경우의 수는 얼마나 될 까?” 하는 의문이 생겼다.

 

경원이를 도와 궁금함을 해결해 주자. 경원이가 판매하는 컬러 그림은 모두 같은 그림이며 흑백 그림도 모두 같은 그림이다.

따라서 경원이가 관심을 두는 것은 컬러인지 아닌지와 각 고객이 구입하는 그림의 개수이다.

 

입력 예 2를 보면

1 2 2 로 첫 번째 고객의 주문이 컬러 2개 흑백 2개로 바뀌었다. 따라서

첫 번째 고객이 구입하는 컬러 그림을 C1, 두 번째 고객이 구입하는 컬러 그림을 C2라고 할 때

(C1, C2) 쌍의 개수는 (1, 1), (1, 2), (2, 1), (2, 2) 가 되어 4가지가 된다.

 

2 2 2 로 두 번째 고객의 주문이 컬러 2개 흑백 2개로 바뀌었다. 컬러 그림의 개수는 변동이 없으므로

(C1, C2) 쌍의 개수는 (1, 1), (1, 2), (2, 1), (2, 2) 가 되어 4가지가 된다.

  


입력형식

첫 행에 두 개의 정수 N, C(1 ≤ N ≤ 100,000, 1 ≤ C ≤ 20)가 입력된다. 두 번째 행에 N개의 ai(i번째 고객이 구입하기 원하는 컬러그림 개수)가 공백으로 구분되어 입력된다. (1 ≤ ai ≤ 1,000,000,000) 세 번째 행에 N개의 bi(i번째 고객이 구입하기 원하는 흑백그림 개수)가 공백으로 구분되어 입력된다. (1 ≤ bi ≤ 1,000,000,000) 네 번째 행에 변경요청 수 Q (1 ≤ Q ≤ 100,000)가 입력된다. 다음 행부터 Q개의 행에 걸쳐 각 행마다 3개의 정수 P, ap, bp가 공백으로 구분하여 입력된다. P는 변경을 요청한 고객 번호이고 ap는 구입하려는 컬러 그림수, bp는 구입하려는 흑백 그림수이다. (1 ≤ P ≤ N), (1 ≤ ap ≤ 1,000,000,000), (1 ≤ bp ≤ 1,000,000,000)

출력형식

출력은 Q개의 행으로 구성된다. 각 변경 요청을 적용할 때 마다 가능한 서로다른 구입방법을 구하여 10,007로 나눈 나머지를 행으로 구분하여 출력한다.

입력 예

2 2
1 1
1 1
1
1 1 1

출력 예

1

입력 예

2 2
1 2
2 3
2
1 2 2
2 2 2

출력 예

4
4

입력 예

4 2
1 2 3 4
1 2 3 4
1
4 1 1

출력 예

66


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP