fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool memory1;
  4.  
  5. typedef int ll;
  6. typedef unsigned long long ull;
  7. typedef double dbe;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<ll> vll;
  10.  
  11. #define openFile(name) freopen((name ".inp"), "r", stdin), freopen((name ".out"), "w", stdout)
  12. #define FOR(i, a, b, x) for (ll i = (a); i <= (b); i += (x))
  13. #define ROF(i, a, b, x) for (ll i = (a); i >= (b); i += (x))
  14. #define fi first
  15. #define se second
  16. #define MASK(x) (1LL << (x))
  17. #define getBit(mask, i) (((mask) >> (i)) & 1)
  18. #define BitOn(mask) (__builtin_popcountll(mask))
  19.  
  20. const int maxN = 1e5 + 2;
  21. const ll LOG = 22;
  22. const ll INF18 = 1e18;
  23. const int INF9 = 1e9;
  24. const ll MOD = 1e9 + 7;
  25.  
  26. struct pii {
  27.     ll x, r, q;
  28.     pii(ll xx = 0, ll rr = 0, ll qq = 0) : x(xx), r(rr), q(qq) {}
  29. };
  30.  
  31. // BIT-of-BIT for 2D queries
  32. struct BIT {
  33.     ll n;
  34.     vector<vector<ll>> b;
  35.     vector<vector<int>> fenw;
  36.     BIT(ll _): n(_), b(n+1) {}
  37.  
  38.     // collect all q-values for each index
  39.     void fakeUpdate(ll i, ll q) {
  40.         for (; i <= n; i += i & -i)
  41.             b[i].push_back(q);
  42.     }
  43.  
  44.     // build inner BITs
  45.     void init() {
  46.         fenw.assign(n+1, {});
  47.         for (ll i = 1; i <= n; i++) {
  48.             auto &v = b[i];
  49.             sort(v.begin(), v.end());
  50.             v.erase(unique(v.begin(), v.end()), v.end());
  51.             fenw[i].assign(v.size() + 1, 0);
  52.         }
  53.     }
  54.  
  55.     // point update
  56.     void update(ll i, ll q) {
  57.         for (; i <= n; i += i & -i) {
  58.             auto &v = b[i];
  59.             ll pos = lower_bound(v.begin(), v.end(), q) - v.begin() + 1;
  60.             for (ll j = pos; j < (ll)fenw[i].size(); j += j & -j)
  61.                 fenw[i][j]++;
  62.         }
  63.     }
  64.  
  65.     // range count of q in [l..r] up to index i
  66.     ll query(ll i, ll l, ll r) {
  67.         ll res = 0;
  68.         for (; i > 0; i -= i & -i) {
  69.             auto &v = b[i];
  70.             ll L = lower_bound(v.begin(), v.end(), l) - v.begin() + 1;
  71.             ll R = upper_bound(v.begin(), v.end(), r) - v.begin();
  72.             for (ll j = R; j > 0; j -= j & -j) res += fenw[i][j];
  73.             for (ll j = L - 1; j > 0; j -= j & -j) res -= fenw[i][j];
  74.         }
  75.         return res;
  76.     }
  77. };
  78.  
  79. ll n, K;
  80. pii a[maxN];
  81. vll valX, valQ;
  82.  
  83. bool cmpR(const pii &A, const pii &B) {
  84.     return A.r > B.r;
  85. }
  86.  
  87. ll getIDlow(const vll &vt, ll val) {
  88.     return lower_bound(vt.begin(), vt.end(), val) - vt.begin() + 1;
  89. }
  90. ll getIDup(const vll &vt, ll val) {
  91.     return upper_bound(vt.begin(), vt.end(), val) - vt.begin();
  92. }
  93.  
  94. ll Solve() {
  95.     // collect coordinates
  96.     FOR(i, 1, n, 1) {
  97.         valX.push_back(a[i].x);
  98.         valX.push_back(a[i].x - a[i].r);
  99.         valX.push_back(a[i].x + a[i].r);
  100.         valQ.push_back(a[i].q);
  101.         valQ.push_back(a[i].q - K);
  102.         valQ.push_back(a[i].q + K);
  103.     }
  104.     sort(valX.begin(), valX.end());
  105.     valX.erase(unique(valX.begin(), valX.end()), valX.end());
  106.     sort(valQ.begin(), valQ.end());
  107.     valQ.erase(unique(valQ.begin(), valQ.end()), valQ.end());
  108.  
  109.     ll sizX = valX.size();
  110.     BIT bit(sizX);
  111.  
  112.     // preprocess fake updates
  113.     FOR(i, 1, n, 1) {
  114.         ll xi = getIDlow(valX, a[i].x);
  115.         ll qi = getIDlow(valQ, a[i].q);
  116.         bit.fakeUpdate(xi, qi);
  117.     }
  118.     bit.init();
  119.  
  120.     ll ans = 0;
  121.     sort(a + 1, a + n + 1, cmpR);
  122.  
  123.     FOR(i, 1, n, 1) {
  124.         ll xi = getIDlow(valX, a[i].x);
  125.         ll L = getIDlow(valX, a[i].x - a[i].r);
  126.         ll R = getIDup(valX, a[i].x + a[i].r);
  127.         ll qi = getIDlow(valQ, a[i].q);
  128.         ll lq = getIDlow(valQ, a[i].q - K);
  129.         ll rq = getIDup(valQ, a[i].q + K);
  130.         if (L <= R)
  131.             ans += bit.query(R, lq, rq) - bit.query(L - 1, lq, rq);
  132.         bit.update(xi, qi);
  133.     }
  134.     return ans;
  135. }
  136.  
  137. void input() {
  138.     cin >> n >> K;
  139.     FOR(i, 1, n, 1) cin >> a[i].x >> a[i].r >> a[i].q;
  140.     cout << Solve();
  141. }
  142.  
  143. int main() {
  144.     ios_base::sync_with_stdio(0);
  145.     cin.tie(0);
  146.     input();
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FAjxrr
language:
C++ (gcc 8.3)
created:
1 day 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!