IOI 2015 day2 1- 말(horses) > 문제은행 : 정보올림피아드&알고리즘




3059 : 말(horses)

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
3 회   

문제

만수르는 조상들과 마찬가지로 말을 키우는 것을 좋아한다. 

그는 카자흐스탄에서 말을 제일 많이 갖고 있다. 

그렇지만 꼭 항상 그랬던 것은 아닌데, N년 전에만 해도 만수르는 그저 젊은이일 뿐이어서 말이 한마리밖에 없었다. 

만수르는 돈을 많이 벌어서 부자가 되고 싶었다.

 

시간순으로 매 해를 0번 해부터 N-1번 해로 번호를 매기자. (즉,N-1 번 해가 가장 최근이다.) 해마다 날씨는 말이 자라는데 영향을 미친다. 

만수르가 기억하기로는, i번 해에 말의 마릿수가 늘어난 비율은 양의 정수 X[i]이다. 

만약 i번 해 연초에 말이 h마리가 있었다면, 그 해 연말에는 말이 모두 hㆍX[i]마리가 된다.

 

말은 매해 연말에만 팔 수 있다. 만수르가 기억하기로 i번 해의 말값은 양의 정수 Y[i]였다. 

즉, 매 해 연말에 갖고 있는 말 중 팔 수 있는 말의 수에는 제약이 없고, 말 한마리 값은 Y[i]로 모두 같다.

 

만수르는 지난 N년 동안, 말을 파는 시기를 잘 정했다면 얼마나 많은 돈을 벌 수 있었을지가 궁금해졌다. 

당신이 만수르를 방문했을 때 이 질문을 받게 되었다.

 

저녁동안 만수르의 기억은 점점 정확해져서, 총 M번의 수정을 하게 된다. 

수정을 한 번 할 때마다 X[i]의 값 중 하나, 또는 Y[i]의 값 중 하나가 바뀐다. 

수정을 한 번 할 때마다 만수르는 말을 팔아서 벌 수 있는 돈의 최대값을 물어본다. 

만수르가 수정할 때마다, 수정된 내용들은 누적된다. 

즉, 만수르에게 대답할 때는 지금까지 만수르가 한 수정들을 모두 반영해야 한다. 

한 X[i]또는 Y[i]가 여러 번 수정되는 경우도 가능하다.

 

만수르의 질문에 대한 답은 매우 큰 수일 수 있다. 

큰 수를 다룰 때 생기는 문제를 피하기 위해서, 답을 10^9 + 7로 나눈 나머지를 알려주면 된다.


N = 3년에 대해서 다음과 같은 정보가 주어졌다고 하자.


















  

 0

 1

 2

 X

 2

 1

 3

 Y

 3

 4

 1

 

이 초기 정보를 가지고, 만수르는 1번 ​해 연말에 모든 말을 다 팔았다면 가장 많은 돈을 벌 수 있다.

  • 전체 과정은 다음과 같다.
  • 처음에 만수르는 말이 한​ 마리 있다.
  • 0번 해 연말에 만수르는 1ㆍX[0] = 2 마리의 말이 있다.
  • 1번 해 연말에 만수르는 2ㆍX[1] = 2 마리의 말이 있다.
  • 이제 말 두 마리를 모두 팔 수 있다. 전체 이익은 2ㆍY[1] = 8이다.

 

이제, M = 1번 수정을 하여 Y[1]이 2로 바뀌었다.
수정 후의 정보는 다음과 같다.


















 

 0

 1

 2

 X

 2

 1

 3

 Y

 3

 2

 1

 

이 경우, 최적해 중 하나는 한 마리를 0번 해 연말에 팔고 2번 해 연말에 세 마리를 파는 것이다.
전체 과정은 다음과 같다.

  • 처음에 만수르는 말이 한 마리 있다.
  • 0번 해 연말에 만수르는 1ㆍX[0] = 2 마리의 말이 있다.
  • 이제 이 중 한 마리를 Y[0] = 3에 팔 수 있고, 한 마리가 남아 있다.
  • 1번 해 연말에 만수르는 1ㆍX[1] = 1 마리의 말이 있다.
  • 2번 해 연말에 만수르는 1ㆍX[2] = 3 마리의 말이 있다.
  • 이제 말 세 마리를 모두 3ㆍY[2] = 3 에 팔 수 있다. 전체 이익은 3 + 3 = 6 이다.

 


N, X, Y 와 수정된 내용의 리스트가 주어진다. 

첫번째 수정을 하기 전과, 매번 수정을 한 다음에 대해서 만수르가 말을 팔아서 벌 수 있는 돈의 최대값을 10^9 + 7로 나눈 나머지를 구하라. 

이를 위해서 함수 init, updateX, updateY를 구현해야 한다.

 

init(N, X, Y) ? 그레이더는 이 함수를 맨 처음 정확히 한 번 호출한다.
 N: 전체 해 수
 X: 길이 N인 배열. 0 ≤ i ≤ N-1 일 때, X[i] 는 i 번 해 연말에 말의 마릿수가 늘어난 비율이다.
 Y: 길이 N인 배열. 0 ≤ i ≤ N-1 일 때, T[i] 는 i 번 해 연말에 말 한마리의 값이다.
 X와 Y는 만수르가 처음에 준 값을 나타낸다. (수정을 하기 전의 값)
 init 함수가 종료한 후, 배열 X와 Y는 유효한 주소에 있으며, 원한다면 이 배열의 내용을 수정할 수 있다.
 이 함수는 X 와 Y 의 초기값을 가지고 만수르가 말을 팔아서 벌 수 있는 돈의 최대값을 10^9 + 7 로 나눈 나머지를 리턴해야 한다.

 

updateX(pos, val)
 pos: 0, ..., N-1 범위 내의 정수.
 val: X[pos] 의 새로운 값.
 이 함수는 주어진 정보에 따라 수정을 한 후, 만수르가 말을 팔아서 벌 수 있는 돈의 최대값을 10^9 + 7 로 나눈 나머지를 리턴해야 한다.

 

updateY(pos, val)
 pos: 0, ..., N-1 범위 내의 정수.
 val: Y[pos] 의 새로운 값.
 이 함수는 주어진 정보에 따라 수정을 한 후, 만수르가 말을 팔아서 벌 수 있는 돈의 최대값을 10^9 + 7 로 나눈 나머지를 리턴해야 한다.

 

모든 X[i] 와 Y[i] 의 값은 항상 (즉, 처음에도, 매번 수정을 한 다음에도) 1 이상 10^9 이하를 만족한다.
init을 호출한 후, 그레이더는 updateX와 updateY를 여러 번 호출할 것이다. updateX와 updateY의 전체 호출 회수는 M 이다. 

 

[부분문제]







































부분문제

점수 

 N

 M

추가적인 계약조건 

 1

17

1 ≤ N ≤ 10

M = 0 

 X[i], Y[i] ≤ 10,

 X[0] * X[1] * ... *X[N - 1] ≤ 1,000

 2

17

1 ≤ N ≤ 1,000​

 

0 ≤ N ≤ 1,000​ 

 없음 

 3

20

 1 ≤ N ≤ 500,000​ 

0 ≤ N ≤ 100,000​ 

 init과 updateXdp 대해서 각각 X[i] ≥ 2이고 val ≥ 2

 4

 23 

1 ≤ N ≤ ​500,000​ ​

 

 

0 ≤ N ≤ 10​,000

 없음

 5

 23 

1 ≤ N ≤ 500,000

 

0 ≤ N ≤ 10​0,000

 

 없음

 


입력형식

line 1: N (1 ≤ N ≤ 500,000) line 2: X[0] … X[N - 1] line 3: Y[0] … Y[N - 1] line 4: M (0 ≤ M ≤ 100,000) lines 5, …, M + 4: type pos val에 해당하는 세 숫자 (type=1이면 updateX이고 type=2이면 updateY).

출력형식

처음 init의 리턴값을 출력하고, 차례로 updateX와 updateY의 모든 호출에 대한 리턴값을 출력한다.

입력 예

3
2 1 3
3 4 1
1
2 1 2

출력 예

8
6


경기도 안양시 동안구 평촌대로 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