[Codeforces Round #827 (Div. 4)] F. Smaller

 

 

---

 

※. 문자열 s 문자열 t 를 q작업했을 때 s,t를 재배열해서 사전순으로 문자열 s가 t보다 작게 만들 수 있는가

 

※. t문자열에 a이외의 다른 문자가 있다면 YES

(s,t 첫 문자열은 "a"에서 시작한다. 문자열마다 a는 무조건 있고 t에 'a' 이외의 다른 문자가 있다면 이 문자를 t문자열 맨 앞에 배치하고 s문자열 맨 앞에는 a를 배치하면 된다.)

 

※. s문자열에만 'a' 이외의 다른 문자가 있다면 NO

(이 경우 t문자열은 'a'로만 이루어져 있기 때문이다.)

 

※. 둘 다 'a'만 있을 경우 s문자열은 t문자열보다 길이가 작아야 한다.

(aaa < aaaa)

 

※. k는 최대 10만까지 문자열 x는 문자열 길이의 합이 50만까지이다.

한번의 작업만 한다면 최대 k = 100,000  x.length() = 500,000 까지 올 수 있다. 이 때 x가 모두 'a'라면 길이를 구해줘야 하기 때문에 길이를 저장해주는 len변수는 long으로 해줘야한다.

 

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//4
public class Main {
	static long ans = 0;
 	public static void main(String arg[]) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringBuilder sb = new StringBuilder();
 		int T = Integer.parseInt(br.readLine());
 		while(T --> 0) {
 			ans = 0;
 			int q = Integer.parseInt(br.readLine());
 			boolean another1 = false;
 			boolean another2 = false;
 			long len1 = 1;
 			long len2 = 1;
 			for(int i = 0; i < q; i++) {
 				boolean answer = false;
 				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 				int d = Integer.parseInt(st.nextToken());
 				int k = Integer.parseInt(st.nextToken());
 				String str = st.nextToken();
 				if(d == 1) {
 					
 					if(!another1) {
 						len1 += (long)str.length()*k;
	 					for(int j = 0; j < str.length(); j++) {
	 						if(str.charAt(j) != 'a')
	 							another1 = true;
	 					}
 					}
 				}
 				else {
 					if(!another2) {
 						len2 += (long)str.length()*k;
	 					for(int j = 0; j < str.length(); j++) {
	 						if(str.charAt(j) != 'a')
	 							another2 = true;
	 					}
 					}
 				}
 				if(another2) {
 					answer = true;
 				}
 				else if(!another1) {
 					if(len1 < len2)
 						answer = true;
 				}
 				
 				if(answer)
 					sb.append("YES").append('\n');
 				else
 					sb.append("NO").append('\n');
 				
 			}
 			
 		}
 		System.out.println(sb);
 	}
}