fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const ll INF = 1e9+7;
  5. const ll MOD = 998244353;
  6. typedef pair<ll,ll> ii;
  7. #define iii pair<ii,ll>
  8. #define f(i,a,b) for(ll i = a;i < b;i++)
  9. #define pb push_back
  10. #define vll vector<ll>
  11. #define F first
  12. #define S second
  13. #define all(x) (x).begin(), (x).end()
  14. ///I hope I will get uprating and don't make mistakes
  15. ///I will never stop programming
  16. ///sqrt(-1) Love C++
  17. ///Please don't hack me
  18. ///@TheofanisOrfanou Theo830
  19. ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
  20. ///Stay Calm
  21. ///Look for special cases
  22. ///Beware of overflow and array bounds
  23. ///Think the problem backwards
  24. ///Training
  25. int main(void){
  26. ios_base::sync_with_stdio(0);
  27. cin.tie(0);
  28. ll n;
  29. cin>>n;
  30. vector<ii>points;
  31. map<ll,vector<ii> > eutheies[2];
  32. set<ll>simeia[2];
  33. f(i,0,n){
  34. ll x,y,l;
  35. cin>>x>>y>>l;
  36. eutheies[0][x].pb(ii(y,y+l));
  37. eutheies[0][x+l].pb(ii(y,y+l));
  38. eutheies[1][y].pb(ii(x,x+l));
  39. eutheies[1][y+l].pb(ii(x,x+l));
  40. simeia[0].insert(x);
  41. simeia[0].insert(x+l);
  42. simeia[1].insert(y);
  43. simeia[1].insert(y+l);
  44. }
  45. f(k,0,2){
  46. for(auto x:simeia[k]){
  47. vector<ii>neo;
  48. for(auto y:eutheies[k][x]){
  49. neo.pb(ii(y.S,y.F));
  50. }
  51. sort(all(neo));
  52. for(auto y:neo){
  53. ii vale = ii(y.S,y.F);
  54. while(!eutheies[k][x].empty() && vale.F <= eutheies[k][x].back().S){
  55. vale.F = min(vale.F,eutheies[k][x][0].F);
  56. eutheies[k][x].pop_back();
  57. }
  58. eutheies[k][x].pb(vale);
  59. }
  60. }
  61. }
  62. for(auto x:simeia[0]){
  63. for(auto X:eutheies[0][x]){
  64. for(auto y:simeia[1]){
  65. for(auto Y:eutheies[1][y]){
  66. if(X.F <= y && y <= X.S && Y.F <= x && x <= Y.S){
  67. points.pb(ii(x,y));
  68. }
  69. }
  70. }
  71. }
  72. }
  73. ll ans = 0;
  74. f(i,0,points.size()){
  75. f(j,0,points.size()){
  76. ii x = points[i],y = points[j];
  77. if(y.F - x.F == y.S - x.S && y.F > x.F){
  78. bool ok = 1;
  79. ll pos = upper_bound(all(eutheies[0][x.F]),ii(x.S,INF)) - eutheies[0][x.F].begin();
  80. pos--;
  81. if(pos == -1){
  82. ok = 0;
  83. }
  84. else{
  85. ok &= eutheies[0][x.F][pos].S >= y.S;
  86. }
  87. pos = upper_bound(all(eutheies[0][y.F]),ii(x.S,INF)) - eutheies[0][y.F].begin();
  88. pos--;
  89. if(pos == -1){
  90. ok = 0;
  91. }
  92. else{
  93. ok &= eutheies[0][y.F][pos].S >= y.S;
  94. }
  95. pos = upper_bound(all(eutheies[1][x.S]),ii(x.F,INF)) - eutheies[1][x.S].begin();
  96. pos--;
  97. if(pos == -1){
  98. ok = 0;
  99. }
  100. else{
  101. ok &= eutheies[1][x.S][pos].S >= y.F;
  102. }
  103. pos = upper_bound(all(eutheies[1][y.S]),ii(x.F,INF)) - eutheies[1][y.S].begin();
  104. pos--;
  105. if(pos == -1){
  106. ok = 0;
  107. }
  108. else{
  109. ok &= eutheies[1][y.S][pos].S >= y.F;
  110. }
  111. ans += ok;
  112. }
  113. }
  114. }
  115. cout<<ans<<"\n";
  116. }
  117. /*
  118. 30
  119. 24 10 2
  120. 20 12 2
  121. 16 12 2
  122. 31 24 29
  123. 18 12 2
  124. 44 121 60
  125. 64 161 20
  126. 19 11 2
  127. 60 70 15
  128. 22 10 2
  129. 84 141 20
  130. 16 10 2
  131. 21 73 14
  132. 45 54 9
  133. 58 35 25
  134. 64 121 20
  135. 45 142 20
  136. 20 10 2
  137. 26 12 2
  138. 42 61 36
  139. 22 12 2
  140. 32 26 6
  141. 52 60 18
  142. 83 160 20
  143. 26 10 2
  144. 49 58 9
  145. 58 39 1
  146. 17 13 2
  147. 28 10 2
  148. 22 30 34
  149.  
  150. Right answer: 52
  151. */
Success #stdin #stdout 0s 5380KB
stdin
Standard input is empty
stdout
0