아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

리본 (Hard)

시간 제한1초메모리 제한1024 MB

요약
정렬된 위치에 놓인 N개의 리본이 각각 길이와 R, Y, B 중 한 색을 가질 때, |Xi - Xj| <= Li + Lj를 만족하면서 색이 다른 두 리본을 찾는다.
난이도

보통10점 중 6점

유형
그리디, 배열, 구현
정답자
아직 제출이 없습니다

문제

당신은 수직선 위에 묶여 있는 NN개의 리본들을 받았다. ii번 (1≤i≤N)(1 \leq i \leq N) 리본은 수직선의 점 X_iX\_i에 묶여 있고, 길이는 L_iL\_i이다. 또한, 그 리본의 색은 C_iC\_i이며 R, Y, B 중 하나이다. (R, Y, B는 각각 빨강, 노랑, 파랑을 나타낸다.)

이제 당신은 리본 두 개를 골라서 매듭을 지으려고 한다. 리본의 탄성이 좋지 않아서 길이를 늘릴 수는 없지만, 구부릴 수는 있다. 즉, ∣X_i−X_j∣≤L_i+L_j\lvert X\_i - X\_j \rvert \le L\_i + L\_j (i≠j)(i \ne j) 를 만족한다면 ii번째와 jj번째 리본으로 매듭을 지을 수 있다. (리본은 면적이 없는 선으로 가정하고 매듭 길이는 무시한다.) 묶인 매듭은 두 리본의 색이 다를 때, 즉 C_i≠C_jC\_i \ne C\_j일 때 아름다운 매듭이라고 부른다.

아름다운 매듭을 지을 수 있는 두 리본의 번호를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 정수 NN이 주어진다.

두 번째 줄에 NN개의 정수 X_1X\_1, X_2X\_2, ⋯\cdots, X_NX\_N이 주어진다.

세 번째 줄에 NN개의 정수 L_1L\_1, L_2L\_2, ⋯\cdots, L_NL\_N이 주어진다.

네 번째 줄에 NN개의 문자 C_1C\_1, C_2C\_2, ⋯\cdots, C_NC\_N이 주어진다.

출력

첫 번째 줄에 정답이 존재한다면 YES, 아니라면 NO를 출력한다.

정답이 존재한다면 두 번째 줄에 아름다운 매듭을 지을 수 있는 두 리본의 번호를 출력한다.

답이 여러 개 존재한다면 아무거나 출력해도 상관없다.

제한

  • 2≤N≤106\color{red}{2 \le N \le 10^6}
  • −109≤X_1<X_2<⋯<X_N≤109-10^9 \le X\_1 < X\_2 < \cdots < X\_{N} \le 10^9
  • 1≤L_i≤1091 \le L\_i \le 10^9
  • C\_i \in \\{R, Y, B\\}

예제2

  1. 예제 1

    입력
    2
    1 3
    1 1
    Y R
    
    예상 출력
    YES
    1 2
    
  2. 예제 2

    입력
    2
    -4 1
    1 2
    B B
    
    예상 출력
    NO