fork download
copy 
  1. /*  chuckie   */
  2. #include <bits/stdc++.h>
  3. //#include "/usr/local/include/bits/stdc++.h"
  4. #define CHUCKIE
  5.  
  6.  
  7. #define cint(d) scanf("%d", &d)
  8. #define cint2(a, b) scanf("%d %d", &a, &b)
  9. #define cint3(a, b, c) scanf("%d %d %d", &a, &b, &c)
  10. #define cint4(a, b, c, d) scanf("%d %d %d %d", &a, &b, &c, &d)
  11.  
  12. #define clong(d) scanf("%lld", &d)
  13. #define clong2(a, b) scanf("%lld %lld", &a, &b)
  14. #define clong3(a, b, c) scanf("%lld %lld %lld", &a, &b, &c)
  15. #define clong4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d)
  16.  
  17. const long long MOD = 1000000007;
  18. const long long MOD2 = 1000000009;
  19. #define MODSET(d) if ((d) >= MOD) d %= MOD;
  20. #define MODR(d) ((d)>=MOD?(d)%MOD:(d))
  21. #define MODNEGSET(d) if ((d) < 0) d = ((d % MOD) + MOD) % MOD;
  22. #define MODADDSET(d) if ((d) >= MOD) d -= MOD;
  23. #define MODADDWHILESET(d) while ((d) >= MOD) d -= MOD;
  24.  
  25. #define MAX 1000000
  26. #define ll long long
  27. #define mp make_pair
  28. #define pb push_back
  29. #define pi acos(-1)
  30. #define NIL -1
  31. #define fi first
  32. #define se second 
  33.  
  34. using namespace std;
  35.  
  36. typedef vector<int> vi;
  37. typedef vector< vi > vvi;
  38. typedef vector<string> vs;
  39. typedef vector<ll> vll;
  40. typedef pair<double,double> dd;
  41. typedef pair<int,int> ii;
  42. typedef pair<ll,ll> pll;
  43. typedef vector< ii > vp;
  44. typedef vector< vp > vvp;
  45.  
  46.  
  47. ll arr[50005];
  48. vector< pll >v;
  49. ll rangesum[50005];
  50.  
  51. bool cmp(const pll &l, const pll &r)
  52. {
  53. 	return l.first<r.first;
  54. }
  55.  
  56.  
  57. ll solve(int i,int l)
  58. {
  59. 	ll ans1=v[i].se*(v[i].se-1)/2;
  60. 	ll ans2=0,ans3=0;
  61.  
  62. 	for(int j=0;j<l;j++)
  63. 	{
  64. 		ll mn=max((ll)1,v[j].fi-2*v[i].fi+1);
  65. 		ll mx=2*v[i].fi + v[j].fi-1;
  66. 		ans3=0;
  67.  
  68. 		//indexes
  69. 		int li=lower_bound(v.begin(),v.end(),pll(mn,-1),cmp)-v.begin();
  70. 		int ui=upper_bound(v.begin(),v.end(),pll(mx,-1),cmp)-v.begin()-1;
  71.  
  72. 		if(j==i)continue;
  73. 		if(li>=l)continue;
  74. 		if(ui<li)continue;
  75. 		//cout<<li<<" "<<ui<<"\n";
  76.  
  77. 		ans3=rangesum[ui+1]-rangesum[li];
  78. 		//cout<<ans2<<"\n";
  79.  
  80. 		if(j>=li && j<=ui)ans3-=(v[j].se);
  81. 		if(i>=li && i<=ui)ans3-=(v[i].se);
  82.  
  83. 		ans3*=v[j].se;
  84. 		//cout<<"ans3 "<<ans3<<" l "<<mn<<" \n";
  85. 		ans2+=ans3;
  86. 	}
  87.  
  88. 	return ans1*ans2/2;
  89. }
  90.  
  91. ll solve2(int i, int l)
  92. {
  93. 	ll ans1=v[i].se*(v[i].se-1)*(v[i].se-2)/6;
  94. 	ll ans2=0;
  95.  
  96.  
  97. 	int j=i;
  98. 		ll mn=max((ll)1,v[j].fi-2*v[i].fi+1);
  99. 		ll mx=2*v[i].fi + v[j].fi-1;
  100.  
  101.  
  102. 		//indexes
  103. 		int li=lower_bound(v.begin(),v.end(),pll(mn,-1),cmp)-v.begin();
  104. 		int ui=upper_bound(v.begin(),v.end(),pll(mx,-1),cmp)-v.begin()-1;
  105.  
  106. 		if(li>=l) return 0;
  107. 		if(ui>=l)ui=l-1;
  108. 		//cout<<li<<" "<<ui<<"\n";
  109.  
  110. 		ans2+=rangesum[ui+1]-rangesum[li];
  111. 		//cout<<ans2<<"\n";
  112.  
  113. 		if(j>=li && j<=ui)ans2-=(v[j].se);
  114.  
  115.  
  116. 	return ans1*ans2;
  117. }
  118.  
  119. int main()
  120. {
  121.  
  122. 	#ifdef CHUCKIE
  123. 	freopen("input.txt","r",stdin);
  124. 	freopen("output.txt","w",stdout);
  125. 	#endif
  126.  
  127. 	ios_base::sync_with_stdio(false);
  128. 	cin.tie(NULL);
  129.  
  130. 	/////////////  code starts here ////////////////
  131.  
  132. 	int t,tc=1;
  133. 	cin>>t;
  134.  
  135. 	while(t--)
  136. 	{
  137. 		int n;
  138. 		cin>>n;
  139. 		v.clear();
  140.  
  141. 		for(int i=0;i<n;i++)
  142. 		{
  143. 			cin>>arr[i];
  144. 		}
  145.  
  146. 		sort(&arr[0],&arr[0]+n);
  147.  
  148. 		v.pb(mp(arr[0],1));
  149. 		int prev=arr[0];
  150.  
  151. 		for(int i=1;i<n;i++)
  152. 		{
  153. 			if(arr[i]==prev)
  154. 			{
  155. 				v.back().se+=1;
  156. 			}
  157. 			else
  158. 			{
  159. 				v.pb(mp(arr[i],1));
  160. 				prev=arr[i];
  161. 			}
  162. 		}
  163.  
  164. 		int l=v.size();
  165.  
  166. 		rangesum[0]=0;
  167. 		for(int i=1;i<=l;i++)
  168. 		{
  169. 			rangesum[i]=rangesum[i-1]+v[i-1].se;
  170. 		}
  171.  
  172. 		ll ans=0,temp=0;
  173. 		for(int i=0;i<l;i++)
  174. 		{
  175. 			temp=0;
  176. 			if(v[i].se>1)
  177. 			temp+=solve(i,l);
  178.  
  179. 			if(v[i].se>2)
  180. 			temp+=solve2(i,l);
  181.  
  182. 			//cout<<temp<<" ";
  183.  
  184. 			ans+=temp;
  185. 		}
  186.  
  187. 		cout<<"Case #"<<tc++<<": "<<ans<<"\n";
  188. 		//cout<<t<<"\n";
  189.  
  190. 	}
  191.  
  192. 	return 0;
  193. }
  194.  
Runtime error #stdin #stdout #stderr 0s 16024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/IoTSHi
language:
C++14 (gcc 8.3)
created:
7 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!