include stdio include stdlib define cmp define point_cont int list 100

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<stdlib.h>
#define cmp(A, B) (((A) > (B)) - ((A) < (B)))
#define point_cont(A,B,C) (((C) >= (A)) && ((C) <= (B)))
int list[100000][2];
int result[100000];
int comp(const void *ap, const void *bp)
{
int *a = (int*) ap;
int *b = (int*) bp;
if(cmp(a[1], b[1]))
{
return cmp(a[1], b[1]);
}
else return cmp(a[0], b[0]);
}
int bin_search_r(int l, int r, int v)
{
while(l<r)
{
int m = ((l+r) >> 1) + ((l+r) & 1);
if(list[m][1] > v)
{
r = m - 1;
}
else
{
l = m;
}
}
return r;
}
int bin_search_l(int l, int r, int v)
{
while(l<r)
{
int m = (l+r) >> 1;
if(list[m][1] < v)
{
l = m + 1;
}
else
{
r = m;
}
}
return l;
}
int bin_search_c(int l, int r, int vd, int vu)
{
while(l<r)
{
int m = (l+r) >> 1;
if(list[m][0] >= vd && list[m][0] <= vu)
{
return 1;
}
if(list[m][0] < vd)
{
l = m + 1;
}
else
{
r = m;
}
}
return list[l][0] >= vd && list[l][0] <= vu;
}
int main()
{
freopen("queries.in","r",stdin);
freopen("queries.out","w",stdout);
int n,i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&list[i][1]);
list[i][0] = i;
}
qsort(list, n, sizeof(int)*2, comp);
/*for(i=0;i<n;i++)
{
fprintf(stderr, "%d %d\n",list[i][0], list[i][1]);
}
fprintf(stderr, "----------\n");*/
int m;
scanf("%d",&m);
for(i=0;i<m;i++)
{
int from, to, val;
scanf("%d%d%d",&from,&to,&val);
from--; to--;
int l_match = bin_search_l(0, n, val);
int r_match = bin_search_r(0, n, val);
//fprintf(stderr,"%d %d\n",l_match, r_match);
if(list[l_match][1] == val && bin_search_c(l_match, r_match, from, to))
{
printf("1");
}
else
{
printf("0");
}
}
printf("\n");
fclose(stdin);
fclose(stdout);
return 0;
}