1613
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <math.h> #include <limits.h> #include <hash_map> using namespace std; //using namespace stdext; // Datatypes typedef vector<int> vi; typedef vector<string> vs; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; // Define #define sz(a) int((a).size()) #define pb push_back #define all(c) (c).begin(),(c).end() #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define FOR(_i,_n) for(int (_i) = 0; (_i) < (_n); (_i)++) #define mp make_pair // Constants const double eps = 1e-8; const double PI = 3.1415926535897932384626433832795; #define INPUT_FILE "feelgood.in" #define OUTPUT_FILE "feelgood.out" hash_map< int, vi > M; int main(void) { #ifdef ALEX freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else //freopen(INPUT_FILE, "r", stdin); //freopen(OUTPUT_FILE, "w", stdout); #endif int N; cin >> N; for(int i = 0; i < N; i++) { int t; scanf("%d", &t); M[t].pb(i); } for(hash_map < int, vi >::iterator it = M.begin(); it != M.end(); it++) { sort((*it).second.begin(), (*it).second.end()); } int K; cin >> K; for(int i = 0; i < K; i++) { int l,r,a; scanf("%d%d%d", &l,&r,&a); l--; r--; if(M.find(a) == M.end()) { printf("%d", 0); } else { if(l == r) { if(binary_search(M[a].begin(), M[a].end(), l) > 0) printf("%d", 1); else printf("%d", 0); continue; } vector<int>::iterator ll = lower_bound(M[a].begin(), M[a].end(), l); vector<int>::iterator rr = lower_bound(M[a].begin(), M[a].end(), r); int d = ll - M[a].begin(); int dd = rr - M[a].begin(); if((M[a][d] == l) || (dd < M[a].size() && M[a][dd] == r)) { printf("%d", 1); continue; } if(ll == M[a].end()) { printf("%d", 0); continue; } if(d != dd) printf("%d", 1); else printf("%d", 0); } } return 0; }
page revision: 0, last edited: 09 May 2008 15:15