CodeForces #549 Div.2 ELynyrd Skynyrd

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

#define N 200000
int n,m,q;
int f[N+5][20];
int pre[N+5];
int p[N+5];
int a[N+5];
int last[N+5];
int res[N+5];


int find(int x,int i)
{
    if(x==0)
        return i;
    int j=0;
    while(1)
    {
        if((int)pow(2.0,j)>x)
            break;
        else
            j++;
    }
    if(f[i][j-1]!=0) {

        x -= (int) pow(2.0, j - 1);
        return find(x, f[i][j - 1]);
    } else
        return -1;
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);

    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i]);
        if(i!=0)
            pre[p[i]]=p[i-1];
    }
    pre[p[0]]=p[n-1];
    memset(last,0,sizeof(last));
    memset(f,0,sizeof(f));
    memset(res,-1,sizeof(res));
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        last[a[i]]=i;
        f[i][0] = last[pre[a[i]]];
        for(int j=1;j<20;j++)
        {
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }

    for(int i=1;i<=m;i++)
    {
        int x=find(n-1,i);
        res[i]=max(res[i-1],x);
    }

    int l,r;
    for(int i=0;i<q;i++)
    {
        scanf("%d%d",&l,&r);
        if(l<=res[r])
            printf("1");
        else
            printf("0");
    }
    printf("\n");


    return 0;
}