fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define scl(x) scanf("%lld",&x)
  5. #define sc(x)  scanf("%d",&x)
  6. #define ll long long
  7. #define lop(i,n) for(int i=0;i<n;++i)
  8. typedef pair<int,int> ii;
  9. typedef pair<ll,ll> pll;
  10.  
  11. const int mN=3e5+10,mC=1e5+10;
  12. struct node{
  13. 	node * L, *R;
  14. 	int sum;
  15. };
  16. int n,c,col[mN];
  17. node * roots[mN];
  18. inline node * build(int s,int e){
  19. 	node *ret=new node();
  20. 	if(s==e){
  21. 		ret->sum=0;
  22. 		return ret;
  23. 	}
  24. 	int m=s+((e-s)>>1);
  25. 	ret->L =build(s,m);
  26. 	ret->R =build(m+1,e);
  27. 	ret->sum=0;
  28. 	return ret;
  29. }
  30. inline node * add(node *r,int s,int e,int idx){
  31. 	node *ret=new node;
  32. 	if(s==e){
  33. 		ret->sum=r->sum+1;
  34. 		return ret;
  35. 	}
  36. 	int m=s+((e-s)>>1);
  37. 	if(idx<=m){
  38. 		ret->L=add(r->L,s,m,idx);
  39. 		ret->R=r->R;
  40. 	}
  41. 	else {
  42. 		ret->R=add(r->R,m+1,e,idx);
  43. 		ret->L=r->L;
  44. 	}
  45. 	ret->sum=r->sum+1;
  46. 	return ret;
  47. }
  48. inline int get(node *a,node *b,int s,int e,int mn){
  49. 	if(s==e){
  50. 		if(b->sum-a->sum>=mn)return s;
  51. 		return 0;
  52. 	}
  53. 	int m=s+((e-s)>>1);
  54. 	if(b->L->sum-a->L->sum>=mn)return get(a->L,b->L,s,m,mn);
  55. 	if(b->R->sum-a->R->sum>=mn)return get(a->R,b->R,m+1,e,mn);
  56. 	return 0;
  57. }
  58. int main(){
  59. #ifndef ONLINE_JUDGE
  60. 	freopen("i.txt","r",stdin);
  61. #endif
  62. 	sc(n),sc(c);
  63. 	roots[0]=build(1,c);
  64. 	for(int i=1;i<=n;++i){
  65. 		sc(col[i]);
  66. 		roots[i]=add(roots[i-1],1,c,col[i]);
  67. 	}
  68. 	int q,a,b,mn;
  69. 	sc(q);
  70. 	lop(i,q){
  71. 		sc(a),sc(b);
  72. 		mn=((b-a+1)>>1) +1;
  73. 		int res=get(roots[a-1],roots[b],1,c,mn);
  74. 		if(res)
  75. 			printf("yes %d\n",res);
  76. 		else puts("no");
  77. 	}
  78. }
  79.  
Runtime error #stdin #stdout 0.04s 22064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YHflVk
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!