ohjtgood- 전국시대 > 문제은행 : 정보올림피아드&알고리즘



4381 : 전국시대

제한시간
1000 ms   
메모리제한
4 MB   
해결횟수
42 회   
시도횟수
298 회   

문제

정올 대륙은 큰 강을 따라 작은 규모의 국가들이 일렬로 길게 늘어서 있다.



 



이 대륙은 강의 상류에서부터 하류까지의 모든 나라들이 강을 공유하고 있기 때문에상류에 있는 나라들이 버린 폐수가 강으로 흘러 들어가, 강 하류
사람들이 피해를 보는 경우가 있다.

 



하류 국가들은 이러한 피해를 명분 삼아 상류 국가들에게 전쟁을 선포하는 경우가 많다.

 



그러나 국가의 크기가 작기 때문에 하나의 국가로써 전쟁하는 것은 불리할 수가 있으므로, 인접한
주변 국가들을 끌어들여 연합을 결성한 후에야 전쟁을 선포한다.

 



이에 맞서 상류 국가들도 인접한 국가끼리 연합을 맺어, 결국에는 상류
연합 대 하류 연합의 구조를 띠게 된다.

 

 



N개의 국가들은 강의 제일 상류에 있는 국가부터 순서대로 a1, a2, … aN의 군사력을 가지고 있다.

 



강 하류에 위치한 j번째 국가가 인접한 국가들끼리 동맹을 맺어 s번째부터 e번째까지의 국가끼리 연합하게 되면이들의 총 군사력은 as+as+1+…aj+…ae-1+ae이다

 

이에 맞서는 i번째 국가가 인접한 국가들끼리 동맹을 맺어 l번째부터 r번째까지의 국가끼리 연합하게 되면마찬가지의 계산법으로 al+al+1+…ai+…ar-1+ar
군사력을 가지게 된다

 

두 연합간의 대결은 단순히 총 군사력이 큰 연합이 이기게 된다

 

 

만약 상류의 i번 국가를 필두로 한 연합이 이긴다면, 그 결과로, j국가의 군사력 aj
반절을 떼어 ai에 더하게 된다.

 

마찬가지로, 하류 국가 연합이 이긴다면, ai의 반절을 aj에 뺏기게 된다(여기서 x의 반절이라 함은, x/2를 반올림 값을 말한다.) 

 

만약 두 연합의 군사력이 같다면, 무승부로 끝나고 아무 일도 일어나지
않는다.



 

 

초기 상태의 모든 나라의 군사력이 주어지고, 현재까지 일어난 모든
전쟁이 어느 연합 대 어느 연합이었는지에 대한 기록이 모두 주어질 때현재 각 나라의 군사력을 모두 출력하는
프로그램을 작성하라.


입력형식

첫 줄에 대륙에 존재하는 국가의 수 N과, 현재까지 전쟁이 일어난 횟수 M이 주어진다.

둘째 줄에 각 국가의 군사력 a1, a2, … aN이 공백을 사이에 두고 주어진다.

셋째 줄부터 시간 순서대로, 전쟁 기록이 l i r s j e 순서대로 주어진다.

 

이는 i번 국가를 필두로 한 l번부터 r번 국가의 연합과 j번 국가를 필두로 한 s번부터 e번 국가까지의 연합이 전투를 했음을 의미한다. 

 

 

부분문제의 제약 조건

 

모든 부분문제에 있어서, 1≤N≤300,000이며, 1≤M≤300,000이다.

모든 국가 x에 있어서, 초기 군사력 ax의 범위는 1≤ax≤50,000이며, a1+a2+...+aN≤​109를 만족한다.

모든 전쟁 기록 입력에서 1≤l≤i≤r<s≤j≤e≤N를 만족한다.

(보다 더 인간적인 표현으로는, [l,r] 연합과 [s,e]연합 양쪽 모두에 속하는 국가는 없다.)

모든 입력값은 정수이다. 

 

타 문제에 비해 메모리 제한이 상당히 제약적이라는 것에 유의한다(4MB).

 

부분문제 1) (총 7점) 모든 전쟁 기록에 있어서, l=i=r이고, s=j=e를 만족한다.

부분문제 2) (총 7점) N≤10이고, M≤100이다.

부분문제 3) (총 13점) N≤70,000이고, 어떤 전쟁 기록이든지, 양쪽 연합에 속한 국가 수를 합쳐도 그 수는 100을 넘지 않는다.

부분문제 4) (총 47점) N≤70,000을 만족한다.

부분문제 5) (총 26점) 주어진 제약조건 외에 아무 제약조건이 없다. ​ 


출력형식

첫째 줄에, 현재 상태의 군사력 a1, a2,…,aN을 공백을 사이에 두고 출력한다.


입력 예

8 2
1 5 2 9 3 8 5 2
1 2 4 6 7 7
2 2 3 4 4 5

출력 예

1 4 2 13 3 8 2 2

출처

ohjtgood

Fenwick Tree

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