농구 토너먼트 > 문제은행



문제은행

3370 : 농구 토너먼트

제한시간: 2000 ms    메모리제한: 512 MB
해결횟수: 1 회    시도횟수: 33 회   



농구 코치인 당신은 n명의 선수들을 관리하며, 이는 1번부터 n번까지 번호가 매겨져 있다.

i번 선수는 a​i cm이다. 당신은 몇 가지 다음과 같은 관계를 발견하였다.

 

  • 함수 f(i , j)는 이는 두 선수의 키의 합이다.
  • P(S)는 선수 집합 S의 모든 순서쌍의 f(i , j)의 합이다. 즉 S에 속하는 모든 선수 i, j에 있어서 
    41062b13833293fe32821aa4621835aa_1559869를 만족한다.
  • 예를 들어, S의 두 선수의 키가 {2, 3} 이라면, P(S) = f(1 , 1) + f(1 , 2) + f(2 , 1) + f(2 , 2) = 4+5+5+6 = 20이다.

 

정올 농구 토너먼트는 방식이 조금 특이하여, 이하 설명을 만족하는 팀만이 출전할 수 있다. 

토너먼트는 m라운드로 진행되며, 각 라운드마다 l, r, x가 주어진다. 

당신은 선수 번호가 구간 [l,r]에 있는 선수들 중, 연속된 번호를 가진 선수들로만 팀을 꾸릴 수 있다.

(예를 들어, l = 1이고 r = 3이면, 선수 1과 선수 3만으로 팀을 꾸릴 수는 없다.) 

이 팀을 집합 S라고 할 때, P(S)가 x 이상이어야만 한다는 규칙이 있다. 

당신은 이 규칙을 만족하면서 그 팀의 선수들의 가장 큰 키가 최소가 되도록 하고 싶다.

 

각 라운드마다 가장 큰 키를 최소화시키는 팀을 꾸릴 때, 그 최소값을 출력하는 프로그램을 작성하라.​ 

 




첫 줄에 두 정수 n, m이 공백을 사이에 두고 주어진다.
다음 줄에 n개의 정수가 공백을 사이에 두고 주어지며, 이는 각 선수들의 키 이다.
그 다음 m줄에 걸쳐서, 각 라운드의 l, r, x값이 주어진다.


부분점수의 제약 조건
모든 입력 데이터에 있어서, 1<=n, m<=300,000, 1<=<=10^7, 1<=l<=r<=n, 1<=x<=10^18을 만족한다.
25점에 해당하는 입력 데이터에 있어, n,m<=5,000을 만족한다.
75점에 해당하는 입력 데이터에 있어, n,m<=50,000을 만족한다.



m줄에 걸쳐, 각 라운드마다 가능한 팀의 가장 큰 키의 최소값을 출력한다.
 만약 어떠한 방법으로도 구간 [l, r]에서 x이상의 P(S)를 가지는 팀을 꾸릴 수 없을 경우, -1을 출력한다.


5 2
1 1 2 3 4
1 5 2
1 5 11
1
2


5 4
1 3 2 4 6
1 3 3
1 3 2
2 4 10
1 1 900
2
1
3
-1






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.