fork(5) download
copy 
  1.  
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<vector>
  6.  
  7. typedef int LL;  //Attention!!
  8. using namespace std;
  9.  
  10.  
  11.  
  12. const int M = 1000000007;
  13.  
  14. struct point{
  15. LL xx;LL yy;LL zz;
  16.  
  17. bool const operator < (const point &b)
  18. const {
  19. return xx < b.xx;
  20. }
  21. };
  22.  
  23. bool myfun(const point& a,const point& b)
  24. {
  25. return a.yy < b.yy;
  26. }
  27.  
  28. const int N = 1000001;
  29. LL tree[N],L[N],R[N];
  30. LL next;
  31. vector <point> v;
  32.  
  33.  
  34. void build(LL ID,LL l,LL r)
  35. {
  36. tree[ID] = 0;
  37. LL m = (l+r)>>1;
  38.  
  39. if(l<r)
  40. {
  41. L[ID] = next++;
  42. build(L[ID],l,m);
  43. R[ID] = next++;
  44. build(R[ID],m+1,r);
  45. }
  46. else
  47. 	{L[ID] = -1;R[ID] = -1;}
  48. }
  49.  
  50. void update(LL ID,LL id,LL l,LL r,LL loc)  //new ID and old id
  51. {
  52. LL m = (l+r)>>1;
  53.  
  54. if(l==r)
  55. 	{
  56. 	tree[ID] = 1;
  57. 	return;	
  58. 	}
  59.  
  60. L[ID] = L[id];
  61. R[ID] = R[id];
  62.  
  63. if(l<=loc && loc<=m)
  64. 	{L[ID] = next++;
  65. 	update(L[ID],L[id],l,m,loc);
  66. 	}
  67. if((m+1)<=loc && loc<=r)
  68. 	{R[ID] = next++;
  69. 	update(R[ID],R[id],m+1,r,loc);	
  70. 	}
  71. tree[ID] = tree[L[ID]] + tree[R[ID]];
  72.  
  73. }
  74.  
  75. LL get(LL id,LL ID,LL k,LL l,LL r)
  76. {
  77. if(l==r) return v[l].xx;
  78.  
  79. LL mid = (l+r)>>1;
  80.  
  81. //cout<<tree[L[ID]] - tree[L[id]]<<' '<<k<<' '<<l<<' '<<r<<endl;
  82.  
  83. if(tree[L[ID]]-tree[L[id]] >= k) 
  84. 		return get(L[id],L[ID],k,l,mid);
  85. else	
  86. 		return get(R[id],R[ID],k-(tree[L[ID]]-tree[L[id]]),mid+1,r);
  87. }
  88.  
  89.  
  90. int main()
  91. {
  92. LL n,i,j,m;
  93.  
  94. cin>>n>>m;
  95.  
  96. v.resize(n);
  97.  
  98. for(i=0;i<n;i++)
  99. 	{cin>>v[i].xx;
  100. 	v[i].yy = i;	
  101. 	}	
  102.  
  103. sort(v.begin(),v.end());
  104.  
  105. for(i=0;i<n;i++)
  106. 	v[i].zz = i;
  107.  
  108. sort(v.begin(),v.end(),myfun);
  109.  
  110. next = 2;
  111.  
  112. build(1,0,n-1);
  113.  
  114. vector <LL> ind(n+1);
  115. ind[0] = 1;
  116.  
  117. for(i=1;i<=n;i++)
  118. 	{
  119. 	ind[i] = next++;	
  120. 	update(ind[i],ind[i-1],0,n-1,v[i-1].zz);
  121. 		//ID and then location
  122. 	}//we set original v[i]'s position in sorted as 1
  123.  
  124. LL a,b,c;
  125.  
  126. sort(v.begin(),v.end());
  127.  
  128. for(i=0;i<m;i++)
  129. 	{
  130. 	cin>>a>>b>>c;
  131. 	a--;
  132. 	cout<<get(ind[a],ind[b],c,0,n-1)<<endl;	
  133. 	}
  134.  
  135. }
  136.  
  137.  
Runtime error #stdin #stdout #stderr 0s 15480KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/3Wce5t
problem MKTHNUM, based on SPOJ submission 17155614 (C++ 4.3.2), 2016-06-22 10:19:51
language:
C++ 4.3.2 (gcc-4.3.2)
created:
9 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!