fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC Optimize("Ofast")
  4. #define rep(i, n)    for(int i = 0; i < (n); ++i)
  5. #define repA(i, a, n)  for(int i = a; i <= (n); ++i)
  6. #define repD(i, a, n)  for(int i = a; i >= (n); --i)
  7. #define trav(a, x) for(auto& a : x)
  8. #define all(x) x.begin(), x.end()
  9. #define sz(x) (int)(x).size()
  10. #define fill(a)  memset(a, 0, sizeof (a))
  11. #define fst first
  12. #define snd second
  13. #define mp make_pair
  14. #define pb push_back
  15. typedef long double ld;
  16. typedef long long ll;
  17. typedef pair<int, int> ii;
  18. typedef pair<ld, ld> pii;
  19. typedef vector<int> vi;
  20. map<ld,int> val;
  21. struct FT {
  22. 		vector<ll> s;
  23. 			FT(int n) : s(n) {}
  24. 				void update(int pos, ll dif) { // a[pos] += dif
  25. 							for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
  26. 								}
  27. 					ll query(int pos) { // sum of values in [0, pos)
  28. 								ll res = 0;
  29. 										for (; pos > 0; pos &= pos - 1) res += s[pos-1];
  30. 												return res;
  31. 													}
  32. 						int lower_bound(ll sum) {// min pos st sum of [0, pos] >= sum
  33. 									// Returns n if no sum is >= sum, or -1 if empty sum is.
  34. 									if (sum <= 0) return -1;
  35. 											int pos = 0;
  36. 													for (int pw = 1 << 25; pw; pw >>= 1) {
  37. 																	if (pos + pw <= sz(s) && s[pos + pw-1] < sum)
  38. 																						pos += pw, sum -= s[pos-1];
  39. 																			}
  40. 															return pos;
  41. 																}
  42. };
  43. struct FT2 {
  44. 		vector<vi> ys; vector<FT> ft;
  45. 			FT2(int limx) : ys(limx) {}
  46. 				void fakeUpdate(int x, int y) {
  47. 							for (; x < sz(ys); x |= x + 1) ys[x].push_back(y);
  48. 								}
  49. 					void init() {
  50. 								trav(v, ys) sort(all(v)), ft.emplace_back(sz(v));
  51. 									}
  52. 						int ind(int x, int y) {
  53. 									return (int)(lower_bound(all(ys[x]), y) - ys[x].begin()); }
  54. 							void update(int x, int y, ll dif) {
  55. 										for (; x < sz(ys); x |= x + 1)
  56. 														ft[x].update(ind(x, y), dif);
  57. 											}
  58. 								ll query(int x, int y) {
  59. 											ll sum = 0;
  60. 													for (; x; x &= x - 1)
  61. 																	sum += ft[x-1].query(ind(x-1, y));
  62. 															return sum;
  63. 																}
  64. };
  65. map<ii,int> cc;
  66. int main() {
  67. 	cin.sync_with_stdio(0); cin.tie(0);
  68. 	cin.exceptions(cin.failbit);
  69. 	int n;ld w;cin>>n>>w;
  70. 	vector<pii> itr;
  71. 	set<ld> al;
  72. 	rep(i,n){
  73. 		ld x,v;cin>>x>>v;
  74. 		itr.pb(mp(abs(x/(v-w)),abs(x/(v+w))));
  75. 		al.insert(abs(x/(v-w)));al.insert(abs(x/(v+w)));
  76. 	}
  77. 	int cnt = 0;
  78. 	trav(i,al){
  79. 		cnt++;
  80. 		val[i] = cnt;
  81. 	}
  82. 	ll ans = 0;
  83. 	FT2 t(200009);
  84. 	trav(i,itr){
  85. 		t.fakeUpdate(val[i.fst],val[i.snd]);
  86. 	}
  87. 	t.init();
  88. 	trav(i,itr){
  89. 		ans+=t.query(200001,val[i.snd]+1)+t.query(val[i.fst]+1,200001)-t.query(val[i.fst],val[i.snd]+1)-t.query(val[i.fst]+1,val[i.snd])-cc[mp(val[i.fst],val[i.snd])];
  90. 		t.update(val[i.fst],val[i.snd],1);
  91. 		cc[mp(val[i.fst],val[i.snd])]++;
  92. 	}
  93. 	cout<<ans;
  94. 	return 0;
  95. }
  96.  
Runtime error #stdin #stdout #stderr 0s 4548KB
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_ios::clear: iostream error
https://ideone.com/WGUMhc
language:
C++14 (gcc 8.3)
created:
6 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!