Advertisement
Guest User

Untitled

a guest
Feb 22nd, 2020
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.13 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. #define ll long long
  7. #define ld long double
  8. #define F first
  9. #define S second
  10. #define pb push_back
  11.  
  12. using namespace std;
  13.  
  14. mt19937_64 gen(time(0));
  15.  
  16. const int maxn = 1e5 + 5;
  17. const int maxa = 1e4 + 5;
  18. const ll mod = 1e9 + 7;
  19.  
  20. pair <int, int> a[maxn];
  21. map <int, vector <pair <int, ll>>> r;
  22. map <int, vector <pair <int, ll>>> c;
  23.  
  24. map <int, vector <pair <int, ll>>> rr;
  25. map <int, vector <pair <int, ll>>> cc;
  26.  
  27. int main()
  28. {
  29. #ifdef LOCAL
  30. freopen("input.txt", "r", stdin);
  31. freopen("output.txt", "w", stdout);
  32. #else
  33. freopen("triangles.in", "r", stdin);
  34. freopen("triangles.out", "w", stdout);
  35. #endif
  36. int n;
  37. cin >> n;
  38. for(int i = 0; i < n; ++i)
  39. {
  40. cin >> a[i].F >> a[i].S;
  41. r[a[i].F].pb({a[i].S, 0});
  42. rr[a[i].F].pb({a[i].S, 0});
  43. c[a[i].S].pb({a[i].F, 0});
  44. cc[a[i].S].pb({a[i].F, 0});
  45. }
  46. for(auto& pp : r)
  47. {
  48. sort(pp.S.begin(), pp.S.end());
  49. ll sum = 0;
  50. ll cnt = 0;
  51. for(int i = int(pp.S.size()) - 2; i >= 0; --i)
  52. {
  53. ++cnt;
  54. sum *= 2;
  55. sum += (pp.S[i + 1].F - pp.S[i].F) * cnt;
  56. sum %= mod;
  57. pp.S[i].S = sum;
  58. }
  59. }
  60.  
  61. for(auto& pp : rr)
  62. {
  63. sort(pp.S.begin(), pp.S.end());
  64. ll sum = 0;
  65. ll cnt = 0;
  66. for(int i = 1; i < int(pp.S.size()); ++i)
  67. {
  68. ++cnt;
  69. sum *= 2;
  70. sum += (pp.S[i].F - pp.S[i - 1].F) * cnt;
  71. sum %= mod;
  72. pp.S[i].S = sum;
  73. }
  74. }
  75.  
  76. for(auto& pp : c)
  77. {
  78. sort(pp.S.begin(), pp.S.end());
  79. ll sum = 0;
  80. ll cnt = 0;
  81. for(int i = int(pp.S.size()) - 2; i >= 0; --i)
  82. {
  83. ++cnt;
  84. sum *= 2;
  85. sum += (pp.S[i + 1].F - pp.S[i].F) * cnt;
  86. sum %= mod;
  87. pp.S[i].S = sum;
  88. }
  89. }
  90.  
  91. for(auto& pp : cc)
  92. {
  93. sort(pp.S.begin(), pp.S.end());
  94. ll sum = 0;
  95. ll cnt = 0;
  96. for(int i = 1; i < int(pp.S.size()); ++i)
  97. {
  98. ++cnt;
  99. sum *= 2;
  100. sum += (pp.S[i].F - pp.S[i - 1].F) * cnt;
  101. sum %= mod;
  102. pp.S[i].S = sum;
  103. }
  104. }
  105. ll ans = 0;
  106. for(int i = 0; i < n; ++i)
  107. {
  108. ll fir1 = (*lower_bound(r[a[i].F].begin(), r[a[i].F].end(), make_pair(a[i].S, -1ll))).S;
  109. ll fir2 = (*lower_bound(rr[a[i].F].begin(), rr[a[i].F].end(), make_pair(a[i].S, -1ll))).S;
  110. ll sec1 = (*lower_bound(c[a[i].S].begin(), c[a[i].S].end(), make_pair(a[i].F, -1ll))).S;
  111. ll sec2 = (*lower_bound(cc[a[i].S].begin(), cc[a[i].S].end(), make_pair(a[i].F, -1ll))).S;
  112. // cerr << i << ' ' << fir << ' ' << sec << endl;
  113. ans += fir1 * sec1 + fir1 * sec2 + fir2 * sec1 + fir2 * sec2;
  114. ans %= mod;
  115. }
  116. cout << ans;
  117. return 0;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement