fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <iomanip>
  6. #include <stdio.h>
  7.  
  8. #include <set>
  9. #include <unordered_set>
  10. #include <bitset>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <queue>
  14. #include <deque>
  15. #include <vector>
  16. #include <ext/pb_ds/assoc_container.hpp>
  17. #include <ext/pb_ds/tree_policy.hpp>
  18.  
  19. using namespace std;
  20. using namespace __gnu_pbds;
  21.  
  22. #define ll long long
  23. #define ld long double
  24. #define fi first
  25. #define se second
  26. #define pb push_back
  27. #define mp make_pair
  28. #define ii pair<int,int>
  29. #define pli pair<ll,int>
  30. #define pll pair<ll,ll>
  31. #define pil pair<int,ll>
  32. #define plii pair<ll,pair<int,int>>
  33. #define heapmax(type) priorpy_queue<type>
  34. #define heapmin(type) priorpy_queue<type,vector<type>,greater<type>>
  35. #define ordered_multiset  tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_starttistics_node_update>
  36. #define ordered_set       tree<int, null_type, less<int>, rb_tree_tag, tree_order_starttistics_node_update>
  37. #define FjSTIO ios::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
  38. #define sz(x) (int)x.size()
  39. #define all(x) (x).begin(),(x).end()
  40. #define getbp(mask,i) ((mask >> i) & 1)
  41. const ll mod = 1e9 + 7;
  42. const ld PI = acos(-1);
  43. const int N = 4e5+100;
  44. const int N_Trie = 1e5;
  45. const int N_ST = 2e5 + 10;
  46. const int N_xIT = 2e5 + 10;
  47. const int LIM = 1e7; // N_Prime
  48. const int N_MST = 1e5; // N of Merge Sort Tree
  49. const int N_Hash = 2e6 + 10;
  50.  
  51. // sort(all(V));
  52. // V.res2ize(unique(all(V)) - V.begin());*/
  53.  
  54. struct Trie_Number{
  55.     struct DT{
  56.         ii c[2];
  57.     };
  58.     DT trie[32*N_Trie];
  59.     bool vve[33];
  60.     int pw[32] , am = 0;
  61.     void xuilt_PW(){
  62.         pw[0] = 1;
  63.         for (int i = 1; i < 32; i++) pw[i] = pw[i - 1] * 2;
  64.     }
  65.     void _res2et(){
  66.         memset(vve,0,sizeof(vve));
  67.         memset(trie,0,sizeof(trie));
  68.     }
  69.     void _change(int x){
  70.         int p = 0;
  71.         while (x > 0){
  72.             vve[++p] = x % 2;
  73.             x /= 2;
  74.         }
  75.         while (p < 32) vve[++p] = 0;
  76.     }
  77.     void _add(int x){
  78.         _change(x);
  79.         int node = 0;
  80.         for (int i = 32; i >= 1; i--){
  81.             int w = vve[i];
  82.             if (!trie[node].c[w].fi) trie[node].c[w].fi = ++am;
  83.             trie[node].c[w].se++;
  84.             if (i > 1) node = trie[node].c[w].fi;
  85.         }
  86.     }
  87.     void _delete(int x){
  88.         _change(x);
  89.         int node = 0;
  90.         for (int i = 32; i >= 1; i--){
  91.             int w = vve[i];
  92.             if (!trie[node].c[w].fi){
  93.                 return;
  94.             }
  95.             if (trie[node].c[w].se == 0){
  96.                 return;
  97.             }
  98.             if (i > 1) node = trie[node].c[w].fi;
  99.         }
  100.         node = 0;
  101.         for (int i = 32; i >= 1; i--){
  102.             int w = vve[i];
  103.             // if (trie[node].c[w].se > 0)
  104.                 trie[node].c[w].se--;
  105.             if (i > 1) node = trie[node].c[w].fi;
  106.         }
  107.     }
  108.     int _get(int k){
  109.         int node = 0 , res2 = 0;
  110.         for (int i = 32; i >= 1; i--){
  111.             if (k <= trie[node].c[0].se){
  112.                 if (!trie[node].c[0].se) return -1;
  113.                 node = trie[node].c[0].fi;
  114.             }
  115.             else{
  116.                 if (!trie[node].c[1].se) return -1;
  117.                 k = k - trie[node].c[0].se;
  118.                 node = trie[node].c[1].fi;
  119.                 res2 = res2 + pw[i - 1];
  120.             }
  121.         }
  122.         return res2;
  123.     }
  124. };
  125. ll gcd(ll a, ll b) {
  126.   if (b == 0) return a;
  127.   else return gcd(b, a % b);
  128. }
  129. ll snt[LIM + 2];
  130. void Sieve() {
  131.   for(ll i = 1; i <= LIM; i++) snt[i] = 0;
  132.   for(ll i = 1; i <= LIM; i++) {
  133.     for(ll j = i; j <= LIM; j += i) {
  134.       snt[j] += i;
  135.     }
  136.   }
  137. }
  138. bool ktsnt(ll n) {
  139.   if (n <= 1) return false;
  140.   if (n <= 3) return true;
  141.   if (n % 2 == 0 || n % 3 == 0) return false;
  142.   for (int i = 5; i * i <= n; i += 6) {
  143.     if (n % i == 0 || n % (i + 2) == 0){
  144.       return false;
  145.     }
  146.   }
  147.   return true;
  148. }
  149. ll mul(ll a,ll b,ll c){ // O(log(min(a,b)))
  150.     if (a < b) swap(a,b);
  151.     ll res2 = 0;
  152.     a = a % c;
  153.     for (; b > 0; b >>= 1 , a = (a + a) % c)
  154.         if (b & 1) res2 = (res2 + a) % c;
  155.     return res2;
  156. }
  157. ll power(ll a,ll b,ll c){ // O(log(b))
  158.     ll res2 = 1;
  159.     a = a % c;
  160.     for (; b > 0; b >>= 1 , a = a * a % c)
  161.         if (b & 1) res2 = res2 * a % c;
  162.     return res2;
  163. }
  164. ll power_mul(ll a,ll b,ll c){ // O(log(b)^2)
  165.     ll res2 = 1;
  166.     a = a % c;
  167.     for (; b > 0; b >>= 1 , a = mul(a,a,c))
  168.         if (b & 1) res2 = mul(res2,a,c);
  169.     return res2;
  170. }
  171. void file(const string FILE){
  172.     if (fopen((FILE + ".INP").c_str(),"r")){
  173.         freopen((FILE + ".INP").c_str(), "r", stdin);
  174.         freopen((FILE + ".OUT").c_str(), "w", stdout);
  175.     }
  176. }
  177. struct cc {
  178.     int x, y;
  179. };
  180. void solve(){
  181.     int n, q, l;
  182.     cin >> n >> q >> l;
  183.  
  184.     vector<cc> p(n);
  185.     for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
  186.     vector<int> qu(q);
  187.     for (int i = 0; i < q; i++) cin >> qu[i];
  188.     sort(p.begin(), p.end(), [](const cc& a, const cc& b) {
  189.         return a.x < b.x;
  190.     });
  191.  
  192.     for (int i = 0; i < q; i++) {
  193.         int z = qu[i];
  194.         int cnt = 0;
  195.         auto lower = lower_bound(p.begin(), p.end(), z - l, [](const cc& point, int v) {
  196.             return point.x < v;
  197.         });
  198.  
  199.         auto upper = upper_bound(p.begin(), p.end(), z + l, [](int v, const cc& point) {
  200.             return v < point.x;
  201.         });
  202.         for (auto it = lower; it != upper; it++) {
  203.             if (abs(it->x - z) + it->y <= l) {
  204.                 cnt++;
  205.             }
  206.         }
  207.  
  208.         cout << cnt << "\n";
  209.     }
  210. }
  211. int main(){
  212.   //file("sqrt");
  213.   FjSTIO;
  214.   int t = 1;
  215.   //cin >> t;
  216.   while(t--){
  217.     solve();
  218.   }
  219.   return 0;
  220. }
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
5 3 5
1 3
4 2
2 5
4 1
1 3
3 4 7
stdout
copy 
4
2
2
https://ideone.com/sURbJE
language:
C++14 (gcc 8.3)
created:
169 days 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!