View difference between Paste ID: hzWPinSS and FnRKRqMj

 #include <iostream>
-#include <cstdlib>
+#include <fstream>
 #include <sstream>
 #include <cstdio>
 #include <cstring>
-#include <string>
+#include <memory.h>
-#include <string.h>
+
 #include <iomanip>
 
 #include <vector>
 #include <queue>
 #include <deque>
 #include <stack>
 #include <set>
-#include <ctime>
+
 #include <list>
-#define pb push_back
+
-#define mp make_pair
+
-#define PI 3.1415926535897932384626433832795
+#define INF (2147483647)
-#define ALL(x) x.begin(), x.end()
+
-#define F first
+
-#define S second
+
-#define m0(x) memset(x,0,sizeof(x))
+class Compressor {
-#define m1(x) memset(x,-1,sizeof(x))
+public:
-#define pw(x) (1ull<<(x))
+	vector<int> v;
 
 	Compressor(vector<int> _a)
-typedef long long ll;
+	{
-typedef unsigned long long ull;
+		v.clear();
-typedef long double ld;
+		sort(_a.begin(), _a.end());
-typedef pair<int,int> pii;
+		v.push_back(-INF);
-const int INF = 2147483647;
+		v.push_back(_a[0]);
-const ll LLINF = 9223372036854775807LL;
+		for(int _i=1; _i<(int)_a.size(); ++_i)
 			if(_a[_i]!=_a[_i-1])
-struct qu {
+				v.push_back(_a[_i]);
-  int l,r,num;
+		v.push_back(INF);
 	}
 	int size()
-const int maxn = 200000;
+	{
-int a[maxn];
+		return v.size();
-int so[maxn];
+	}
-int ans[maxn];
+	int get(int a)
-int col[maxn];
+	{
-int p[maxn];
+		return lower_bound(v.begin(), v.end(), a) - v.begin();
-int n,qc;
+	}
-qu q[maxn];
+
-int sc = 0;
+vector<int> vv[70000];
-int bl;
+
 int main()
-bool comp(int a, int b) {
+{
-  return (q[a].l/bl<q[b].l/bl) || (q[a].l/bl==q[b].l/bl && q[a].r<q[b].r);
+	ios_base::sync_with_stdio(0);
-}
+
 	vector<int> m;
-int main() {
+	int n;
-  //freopen("input.txt", "r", stdin);
+	cin>>n;
-  //freopen("output.txt", "w", stdout);
+	int i, l, r, a;
-  cin >> n;
+	for(i=1;i<=n;++i){
-  for (int i=0;i<n;i++) {
+		cin>>a;
-    scanf("%d", &a[i]);
+		m.push_back(a);
-    so[sc++] = a[i];
+	}
-  }
+	Compressor comp(m);
-  bl = (int)(sqrt(n));
+	for(i=0; i<(int)m.size(); ++i){
-  cin >> qc;
+		vv[comp.get(m[i])].push_back(i+1);
-  for (int i=0;i<qc;i++) {
+	}
-    scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].num);
+	sort(m.begin(), m.end());
-    so[sc++] = q[i].num;
+	cin>>n;
-  }
+	for(i=0;i<n;++i){
-  sort(so, so+sc);
+		cin>>l>>r>>a;
-  for (int i=0;i<n;i++) a[i] = (int)(lower_bound(so, so+sc, a[i])-so);
+		int t = lower_bound(m.begin(), m.end(), a) - m.begin();
-  for (int i=0;i<qc;i++) q[i].num = (int)(lower_bound(so, so+sc, q[i].num)-so);
+		if(t<n && m[t]==a){
-  for (int i=0;i<qc;i++) p[i] = i;
+			t = comp.get(a);
-  sort(p, p+qc, comp);
+			int tt = lower_bound(vv[t].begin(), vv[t].end(), l)-vv[t].begin();
-  int l = 0, r = -1;
+			if(tt<(int)vv[t].size() && vv[t][tt]<=r) cout<<1;
-  for (int i=0;i<qc;i++) {
+			else cout<<0;
-    qu &cur = q[p[i]];
+
-    cur.l--; cur.r--;
+		}else cout<<0;
-    while (r<cur.r) {
+	}
-      r++;
+
-      col[a[r]]++;
+	return 0;
-    }
+