Codeforces 1169E 매우 어렵습니다.

5964 단어
E. And Reachability
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Toad Pimple has an array of integers a1,a2,…,ana1,a2,…,an.
We say that yy is reachable from xx if x0api&api+1>0 for all integers ii such that 1≤iHere && denotes the bitwise AND operation.
You are given qq pairs of indices, check reachability for each of them.
Input
The first line contains two integers nn and qq (2≤n≤3000002≤n≤300000, 1≤q≤3000001≤q≤300000) — the number of integers in the array and the number of queries you need to answer.
The second line contains nn space-separated integers a1,a2,…,ana1,a2,…,an (0≤ai≤3000000≤ai≤300000) — the given array.
The next qq lines contain two integers each. The ii-th of them contains two space-separated integers xixi and yiyi (1≤xiOutput
Output qq lines. In the ii-th of them print "Shi"if yiyi is reachable from xixi, otherwise, print "Fou".
Example
input
Copy 
5 3
1 3 0 2 1
1 3
2 4
1 4

output
Copy 
Fou
Shi
Shi

Note
In the first example, a3=0a3=0. You can't reach it, because AND with it is always zero. a2&a4>0a2&a4>0, so 44 is reachable from 22, and to go from 11 to 44 you can use p=[1,2,4]p=[1,2,4]. 
#include
#include
#define maxn 300010
using namespace std;
int n,q,a[maxn],dp[maxn][30],las[30];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=0;i<20;i++){
        las[i]=n+1;
        dp[n+1][i]=n+1;
    }
    for(int i=n;i>=1;i--){
        for(int j=0;j<20;j++)
            dp[i][j]=n+1;
        for(int j=0;j<20;j++){
            if(a[i]&(1<<j)){
                for(int k=0;k<20;k++)
                    dp[i][k]=min(dp[i][k],dp[las[j]][k]);
                las[j]=i;
                dp[i][j]=i;
            }
        }
    }
    int x,y;
    while(q--){
        cin>>x>>y;
        bool f=0;
        for(int i=0;i<20;i++){
            if(a[y]&(1<y){
                f=1;
                break;
            }
        }
        if(f)puts("Shi");
        else puts("Fou");
    }
    return 0;
}
JavaScript에서 객체를 동결하는 방법: Object.동결(), 객체.seal () & 추가
SVM 조정 주식 예측

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage