fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define FOR(i, a, b) for (int i = a; i <= b; ++i)
  4. #define FORD(i, a, b) for (int i = a; i >= b; --i)
  5. #define ll long long
  6.  
  7. using namespace std;
  8.  
  9. const int N = 2e5 + 5;
  10. const int delta = 55;
  11. int sub, n, q;
  12. ll dp[N][delta];
  13. vector<int> val;
  14. vector<int> ID[N], POS[N];
  15.  
  16. struct Student {
  17.     int x, r, t;
  18.     void input() {
  19.         cin >> x >> r >> t;
  20.     }
  21. } Students[N];
  22.  
  23. struct Fenwick_Tree {
  24.     int n;
  25.     vector<int> bit;
  26.     Fenwick_Tree(int _n = 0) {
  27.         n = _n;
  28.         bit.assign(n + 5, 0);
  29.     }
  30.     void upd(int x, int value) {
  31.         for (; x <= n; x += x & -x) bit[x] += value;
  32.     }
  33.     int get(int x) {
  34.         int ans = 0;
  35.         for (; x; x -= x & -x) ans += bit[x];
  36.         return ans;
  37.     }
  38.     int get_range(int l, int r) {
  39.         if (l > r) return 0;
  40.         if (l <= 1) return get(r);
  41.         return get(r) - get(l - 1);
  42.     }
  43. };
  44.  
  45. void nhap() {
  46.     cin >> sub >> n >> q;
  47.     FOR(i, 1, n) Students[i].input();
  48. }
  49.  
  50. bool cmp(const int &x, const int &y) {
  51.     return Students[x].r > Students[y].r;
  52. }
  53.  
  54. ll Count1(vector<int> &idList, vector<int> &posList) {
  55.     if (idList.empty()) return 0;
  56.     sort(idList.begin(), idList.end(), cmp);
  57.     sort(posList.begin(), posList.end());
  58.     posList.resize(unique(posList.begin(), posList.end()) - posList.begin());
  59.  
  60.     ll ans = 0;
  61.     Fenwick_Tree bit((int)posList.size());
  62.  
  63.     for (int it : idList) {
  64.         int l = Students[it].x - Students[it].r;
  65.         int r = Students[it].x + Students[it].r;
  66.  
  67.         int L = lower_bound(posList.begin(), posList.end(), l) - posList.begin() + 1;
  68.         int R = upper_bound(posList.begin(), posList.end(), r) - posList.begin();
  69.         if (L <= R) ans += bit.get_range(L, R);
  70.  
  71.         int idxpos = lower_bound(posList.begin(), posList.end(), Students[it].x) - posList.begin() + 1;
  72.         bit.upd(idxpos, 1);
  73.     }
  74.     return ans;
  75. }
  76.  
  77. ll Count2(const vector<int> &BigID, const vector<int> &posList, const vector<int> &LowID, bool flag) {
  78.     if (BigID.empty() || LowID.empty() || posList.empty()) return 0;
  79.     ll ans = 0;
  80.     Fenwick_Tree bit((int)posList.size());
  81.  
  82.     int j = 0;
  83.     for (int it : LowID) {
  84.         while (j < (int)BigID.size() && Students[BigID[j]].r >= (flag ? Students[it].r : (Students[it].r + 1))) {
  85.             int idxpos = lower_bound(posList.begin(), posList.end(), Students[BigID[j]].x) - posList.begin() + 1;
  86.             bit.upd(idxpos, 1);
  87.             j++;
  88.         }
  89.  
  90.         int l = Students[it].x - Students[it].r;
  91.         int r = Students[it].x + Students[it].r;
  92.         int L = lower_bound(posList.begin(), posList.end(), l) - posList.begin() + 1;
  93.         int R = upper_bound(posList.begin(), posList.end(), r) - posList.begin();
  94.         if (L <= R) ans += bit.get_range(L, R);
  95.     }
  96.     return ans;
  97. }
  98.  
  99. void init() {
  100.     val.clear();
  101.     FOR(i, 1, n) val.push_back(Students[i].t);
  102.     sort(val.begin(), val.end());
  103.     val.resize(unique(val.begin(), val.end()) - val.begin());
  104.  
  105.     int m = (int)val.size();
  106.     FOR(i, 1, m) {
  107.         ID[i].clear();
  108.         POS[i].clear();
  109.     }
  110.  
  111.     FOR(i, 1, n) {
  112.         int comp = lower_bound(val.begin(), val.end(), Students[i].t) - val.begin() + 1;
  113.         Students[i].t = comp;
  114.         ID[comp].push_back(i);
  115.         POS[comp].push_back(Students[i].x);
  116.     }
  117.  
  118.     FOR(cnt, 1, m) {
  119.         sort(ID[cnt].begin(), ID[cnt].end(), [&](int a, int b){
  120.             return Students[a].r > Students[b].r;
  121.         });
  122.         sort(POS[cnt].begin(), POS[cnt].end());
  123.         POS[cnt].resize(unique(POS[cnt].begin(), POS[cnt].end()) - POS[cnt].begin());
  124.     }
  125.  
  126.     FOR(i, 1, m) dp[i][0] = Count1(ID[i], POS[i]);
  127.  
  128.     FOR(i, 1, m) {
  129.         FOR(j, i + 1, m) {
  130.             if (val[j - 1] - val[i - 1] >= delta) break;
  131.             ll cur = Count2(ID[i], POS[i], ID[j], 1) + Count2(ID[j], POS[j], ID[i], 0);
  132.             dp[i][j - i] = cur + dp[i][j - i - 1];
  133.         }
  134.     }
  135. }
  136.  
  137. void giai() {
  138.     while (q--) {
  139.         int l, r;
  140.         cin >> l >> r;
  141.         int L = lower_bound(val.begin(), val.end(), l) - val.begin() + 1;
  142.         int R = upper_bound(val.begin(), val.end(), r) - val.begin();
  143.  
  144.         ll ans = 0;
  145.         FOR(i, L, R) ans += dp[i][R - i];
  146.         cout << ans << ' ';
  147.     }
  148. }
  149.  
  150. int main() {
  151.     ios_base::sync_with_stdio(0);
  152.     cin.tie(0); cout.tie(0);
  153.  
  154.     #define name "lovesharing"
  155.  
  156.     if (fopen(name".inp", "r")) {
  157.         freopen(name".inp", "r", stdin);
  158.         freopen(name".out", "w", stdout);
  159.     }
  160.  
  161.     nhap();
  162.     init();
  163.     giai();
  164.  
  165.     return 0;
  166. }
  167.  
Success #stdin #stdout 0.01s 15856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cOGo5J
language:
C++14 (clang 8.0)
created:
5 hours 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!