AOJ ZEROONE

 

SOL)

완전 탐색으로는 시간 초과 이므로

table[n]을 작성한다. table[n]은 0번째부터 n번째까지의 1의 개수

 

경우의 수는 3가지

1번째 max = 1, min = 1

2번째 max = 0, min = 0

3번째 max = 1, min = 0

[-] Collapse

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[1000000];
int table[1000000];

int main(){
    scanf("%s", str);
    int len = strlen(str);
    table[0] = str[0] - '0';
    for (int i = 1; i < len; i++)
        table[i] = str[i] - '0' + table[i - 1];

    int T; scanf("%d", &T);
    int i, j;
    while (T--){
        scanf("%d%d", &i, &j);
        if (i > j) swap(i, j);
        //max =1, min = 1인 경우
        if (str[i] == '1' && j - i == table[j] - table[i]) puts("Yes");
        //max = 0, min = 0인 경우
        else if (str[i] == '0' && table[j] == table[i]) puts("Yes");    
        //max = 1, min = 0인 경우
        else puts("No");
    }
}