fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define gc getchar_unlocked
  4.  
  5. #include <ext/pb_ds/assoc_container.hpp>
  6. #include <ext/pb_ds/tree_policy.hpp>
  7. #include <ext/pb_ds/detail/standard_policies.hpp>
  8. using namespace __gnu_pbds;
  9. using namespace std;
  10. #define pii pair<int, int>
  11. #define fo(i, n) for(i=0; i<n; i++)
  12. typedef tree< pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> mset;
  13. struct os{
  14. 	mset A;
  15. 	int T;
  16. 	#define ook order_of_key
  17. 	#define fbo find_by_order
  18. 	#define INF INT_MAX
  19. 	#define var int
  20. 	os(){
  21. 		T = 0;
  22. 	}
  23. 	//add x to set
  24. 	void add(var x){
  25. 		A.insert({x, ++T});
  26. 	}
  27.  
  28. 	//no of elements in set between [l,r]
  29. 	int count(int l, int r){
  30. 		int no = A.ook({r, INF});
  31. 		no -= A.ook({l, 0});
  32. 		return no;
  33. 	}
  34. 	//erase x from set
  35. 	void erase(var x){
  36. 		A.erase(A.lower_bound({x, 0}));
  37. 	}
  38. 	//get random element from set
  39. 	var rnd(int del = 0){
  40. 		int n = A.size();
  41. 		int pos = rand()%n;
  42. 		pair<var,int> x = *(A.fbo(pos));
  43. 		if(del) erase(x.first);
  44. 		return x.first;
  45. 	}
  46. };
  47. #define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
  48. #define ll long long
  49. #define si(x)	scanf("%d",&x)
  50. #define sl(x)	scanf("%lld",&x)
  51. #define ss(s)	scanf("%s",s)
  52. #define pi(x)	printf("%d\n",x)
  53. #define pl(x)	printf("%lld\n",x)
  54. #define ps(s)	printf("%s\n",s)
  55. #define pb push_back
  56. #define mp make_pair
  57. #define F first
  58. #define S second
  59. #define all(x) x.begin(), x.end()
  60. #define clr(x) memset(x, 0, sizeof(x))
  61. #define sortall(x) sort(all(x))
  62. #define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
  63. #define PI 3.1415926535897932384626
  64. typedef pair<ll, ll>	pl;
  65. typedef vector<int>		vi;
  66. typedef vector<ll>		vl;
  67. typedef vector<pii>		vpii;
  68. typedef vector<pl>		vpl;
  69. typedef vector<vi>		vvi;
  70. typedef vector<vl>		vvl;
  71. int mpow(int base, int exp); 
  72. void ipgraph(int m);
  73. void dfs(int u, int par);
  74. const ll mod = 1000000007;
  75. const ll mod2 = 1000000007 * 1LL * 1000000007;
  76. const int N = 3e5, M = N;
  77. void MOD2(ll &x){
  78. 	if(x >= mod2) x-=mod2;
  79. 	if(x<0) x+=mod2;
  80. }
  81. //=======================
  82.  
  83. vi g[N];
  84. int a[N], A[N], n;
  85. ll sum[N];
  86. int bit[20][N], pre[N];
  87. map<ll, ll> h, rev;
  88. set<int> pos[N];
  89. os my[N];
  90. int hai(int no, int x, int y){
  91. 	if(pos[no].empty()) return 0;
  92. 	auto it = pos[no].lower_bound(x);
  93. 	if(it == pos[no].end()) return 0;
  94. 	int at = *it;
  95. 	if(at <= y) return 1;
  96. 	return 0;
  97. }
  98. ll r(){
  99. 	return rand()*32000LL+rand();	
  100. }
  101. void add(int pos, int val){
  102. 	while(pos<N){
  103. 		my[pos].add(val);
  104. 		pos += pos&(-pos);
  105. 	}
  106. }
  107. int query(int pos, int val){
  108. 	int ans = 0;
  109. 	while(pos){
  110. 		ans += my[pos].count(0, val);
  111. 		pos -= pos&(-pos);
  112. 	}
  113. 	return ans;
  114. }
  115. int renk(int x, int l, int r){
  116. 	return query(r, x) - query(l-1, x);	
  117. }
  118. void precompute(){
  119. 	int i, j;	
  120. 	Fo(i, 1, n+1) {
  121. 		add(i, A[i]);
  122. 		pos[A[i]].insert(i);
  123. 		if(h[A[i]]) continue;
  124. 		h[A[i]] = (r()*3200LL+r())%mod2;
  125. 		rev[h[A[i]]] = A[i];
  126.  
  127. 	}
  128. 	sum[0] = pre[0] = 0;
  129. 	Fo(i, 1, n+1){
  130. 		MOD2(sum[i] = h[A[i]]+sum[i-1]);
  131. 		pre[i] = pre[i-1]^A[i];
  132. 		int no = A[i];
  133. 		Fo(j, 0, 20){
  134. 			if( (1<<j) & no ){
  135. 				bit[j][i] = no;
  136. 			}
  137. 		}
  138. 	}
  139. 	Fo(j, 0, 20)
  140. 	Fo(i, 1, n+1) bit[j][i] ^= bit[j][i-1];
  141.  
  142. }
  143.  
  144. #define deb(x) cout << #x << "=" << x << endl
  145. #define deb2(x, y) cout << #x << "=" << x <<", " <<#y << "="<< y << endl
  146. void solve(){
  147. 	int i, q, a, b, c, d, k, j;
  148. 	cin >> n >> q;
  149. 	Fo(i, 1, n+1) cin >> A[i], pos[A[i]].clear(), my[i].A.clear(), my[i].T = 0, sum[i] = 0;
  150. 	fo(j, 20)
  151. 	Fo(i, 1, n+1) bit[j][i] = 0;
  152. 	h.clear();
  153. 	rev.clear();
  154. 	precompute();
  155.  
  156. 	// Fo(i, 1, n+1) cout << h[A[i]] << " "; cout << endl;
  157.  
  158. 	while(q--){
  159. 		cin >> a >> b >> c >> d;
  160. 		ll h1, h2;
  161. 		MOD2(h1 = sum[b] - sum[a-1]);
  162. 		MOD2(h2 = sum[d] - sum[c-1]);
  163. 		// deb2(h1, h2);
  164. 		if(h1 == h2){
  165. 			cout << "YES\n";
  166. 			continue;
  167. 		}
  168.  
  169. 		int x1 = pre[b] ^ pre[a-1];
  170. 		int x2 = pre[d] ^ pre[c-1];
  171. 		int xy = x1 ^ x2;
  172. 		// deb2(x1,x2);
  173. 		// deb(xy);
  174. 		if(xy == 0){
  175. 			cout << "NO\n";
  176. 			continue;
  177. 		}
  178. 		Fo(k, 0, 30){
  179. 			if( xy & (1<<k) ) break;
  180. 		}
  181. 		int p1 = bit[k][b] ^ bit[k][a-1];
  182. 		int p2 = bit[k][d] ^ bit[k][c-1];
  183. 		// deb(k);
  184. 		// deb2(p1, p2);
  185.  
  186. 		int no = p1^p2;
  187. 		if(no == 0) {
  188. 			cout << "NO\n";
  189. 			continue;
  190. 		}
  191. 		// deb(no);
  192. 		int f1 = hai(no, a, b);
  193. 		int f2 = hai(no, c, d);
  194. 		int check = f1 + f2;
  195. 		if(check == 0) {
  196. 			cout << "NO\n";
  197. 			continue;
  198. 		}
  199. 		int poss = 1;
  200.  
  201. 		// deb2(f1,f2);
  202. 		if(!f1) swap(a, c), swap(b, d), swap(h1, h2);
  203.  
  204. 		//YAHA SE >>>>>>>>>>>>>>>>>>>>>>>>
  205. 		//a,b mei hai
  206. 		ll com;
  207. 		MOD2(com = h1 - h[no]);
  208.  
  209. 		ll other_ki_hash ;
  210. 		MOD2(other_ki_hash = h2 - com);
  211. 		// deb2(com, other_ki_hash);
  212. 		int other_no = rev[other_ki_hash];
  213. 		// deb(other_no);
  214. 		if(other_no == 0){
  215. 			poss = 0;
  216. 			// cout <<"NO\n";
  217. 			// continue;
  218. 		}
  219. 		int ff = other_no^no;
  220. 		// deb(ff);
  221. 		if(ff != xy){
  222. 			poss = 0;
  223. 			// cout <<"NO\n";
  224. 			// continue;
  225. 		}
  226. 		// deb(other_no);
  227. 		if(hai(other_no, c, d)){
  228. 			//so we solved some other variant of problem
  229. 			//for current problem,
  230. 			// check for renk
  231. 			int e1 = 0, e2 = 0;
  232. 			// deb2(no, other_no);
  233. 			int jno = no, jother = other_no;
  234. 			if(no>other_no) jno--, e1 = 1;
  235. 			else if(no<other_no) jother--, e2 = 1;
  236. 			int r1 = e1+renk(jno, a, b);
  237. 			int r2 = e2+renk(jother, c, d);
  238. 			// deb2(e1,e2);
  239. 			// deb2(r1,r2);
  240. 			if(r1==r2){
  241. 				poss = 1;
  242. 				// cout << "YES\n";
  243. 			}
  244. 			else{
  245. 				poss = 0;
  246. 				// cout <<"NO\n";
  247. 			}
  248. 		}
  249. 		else{
  250. 			poss = 0;
  251. 			// cout <<"NO\n";
  252. 		}
  253. 		//YAHA TAK >>>>>>>>>>>>>>>>>>>>>
  254. 		//MAINE DALA <<<<<<<<<<
  255. 		if(check == 2 and poss == 0){
  256. 			swap(a, c), swap(b, d), swap(h1, h2);
  257. 			ll com;
  258. 			MOD2(com = h1 - h[no]);
  259.  
  260. 			ll other_ki_hash ;
  261. 			MOD2(other_ki_hash = h2 - com);
  262. 			// deb2(com, other_ki_hash);
  263. 			int other_no = rev[other_ki_hash];
  264. 			// deb(other_no);
  265. 			if(other_no == 0){
  266. 				poss = 0;
  267. 				// cout <<"NO\n";
  268. 				// continue;
  269. 			}
  270. 			int ff = other_no^no;
  271. 			// deb(ff);
  272. 			if(ff != xy){
  273. 				poss = 0;
  274. 				// cout <<"NO\n";
  275. 				// continue;
  276. 			}
  277. 			// deb(other_no);
  278. 			if(hai(other_no, c, d)){
  279. 				//so we solved some other variant of problem
  280. 				//for current problem,
  281. 				// check for renk
  282. 				int e1 = 0, e2 = 0;
  283. 				// deb2(no, other_no);
  284. 				int jno = no, jother = other_no;
  285. 				if(no>other_no) jno--, e1 = 1;
  286. 				else if(no<other_no) jother--, e2 = 1;
  287. 				int r1 = e1+renk(jno, a, b);
  288. 				int r2 = e2+renk(jother, c, d);
  289. 				// deb2(e1,e2);
  290. 				// deb2(r1,r2);
  291. 				if(r1==r2){
  292. 					poss = 1;
  293. 					// cout << "YES\n";
  294. 				}
  295. 				else{
  296. 					poss = 0;
  297. 					// cout <<"NO\n";
  298. 				}
  299. 			}
  300. 			else{
  301. 				poss = 0;
  302. 				// cout <<"NO\n";
  303. 			}
  304. 		}
  305.  
  306. 		cout << (poss?"YES\n":"NO\n");
  307. 		//overrr
  308. 	}
  309. }
  310. int main()
  311. {
  312. 	ios_base::sync_with_stdio(false);
  313. 	cin.tie(NULL);
  314. 	srand(time(NULL));
  315. 	int i,n,k,j,t;
  316. 	cin >> t;
  317. 	while(t--) solve();
  318.  
  319. 	return 0;
  320. } 
  321.  
Success #stdin #stdout 0.01s 96256KB
comments (?)
stdin
copy 
4
12 1
2 1 3 2 3 2 3 2 3 1 3 3
1 7 6 12
6 3
1 3 4 2 3 4
1 3 4 6
1 2 5 6
3 5 2 4 

12 1
2 1 3 2 3 2 3 2 3 1 3 3
1 7 6 12
6 3
1 3 4 2 3 4
1 3 4 6
1 2 5 6
3 5 2 4
stdout
copy 
YES
YES
NO
YES
YES
YES
NO
YES
https://ideone.com/jPAHvd
cloning codechef june long
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!