fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pii pair < int , int >
  4. #define fi first
  5. #define se second
  6. #define all(data) data.begin(),data.end()
  7. using namespace std;
  8.  
  9. const int N = 3e5;
  10. const int inf32 = 1e9;
  11. const int inf64 = 1e18;
  12. const int LOG = 20;
  13. const int mod = 1e9 + 7;
  14. const int base = 2e6;
  15.  
  16. int n , cntX , cntY , q;
  17. unordered_map < int , int > mx , my;
  18. vector < int > Cx[N + 5] , Cy[N + 5];
  19.  
  20. void Shinai()
  21. {
  22.     ios_base::sync_with_stdio(0);
  23.     cin.tie(0);
  24.     cout.tie(0);
  25.     #define TASK "20250924"
  26.     if(fopen(TASK".INP" , "r"))
  27.     {
  28.         freopen(TASK".INP" , "r" , stdin);
  29.         freopen(TASK".OUT" , "w" , stdout);
  30.     }
  31. }
  32.  
  33. void process()
  34. {
  35.     for(int i = 1 ; i <= cntX ; i ++) sort(Cx[i].begin() , Cx[i].end());
  36.     for(int i = 1 ; i <= cntY ; i ++) sort(Cy[i].begin() , Cy[i].end());
  37.     cin >> q;
  38.     while(q --)
  39.     {
  40.         int x , y , u , v , c , id;
  41.         int res = 0;
  42.         cin >> x >> y >> u >> v;
  43.         id = mx[x];
  44.         if(id != 0)
  45.             res += upper_bound(Cx[id].begin() , Cx[id].end() , v) - lower_bound(Cx[id].begin() , Cx[id].end() , y);
  46.         id = mx[u];
  47.         if(id != 0)
  48.             res += upper_bound(Cx[id].begin() , Cx[id].end() , v) - lower_bound(Cx[id].begin() , Cx[id].end() , y);
  49.         id = my[y];
  50.         if(id != 0)
  51.             res += upper_bound(Cy[id].begin() , Cy[id].end() , u - 1) - lower_bound(Cy[id].begin() , Cy[id].end() , x + 1);
  52.         id = my[v];
  53.         if(id != 0)
  54.             res += upper_bound(Cy[id].begin() , Cy[id].end() , u - 1) - lower_bound(Cy[id].begin() , Cy[id].end() , x + 1);
  55.         cout << res << '\n';
  56.     }
  57.  
  58. }
  59.  
  60. void read()
  61. {
  62.     cin >> n;
  63.     for(int i = 1 ; i <= n ; i ++)
  64.     {
  65.         int x , y; cin >> x >> y;
  66.         if(mx[x] == 0) mx[x] = ++cntX;
  67.         Cx[mx[x]].emplace_back(y);
  68.         if(my[y] == 0) my[y] = ++cntY;
  69.         Cy[my[y]].emplace_back(x);
  70.     }
  71. }
  72.  
  73. int main()
  74. {
  75.     Shinai();
  76.     int test_case;
  77.     test_case = 1;
  78.     //cin >> test_case;
  79.     while(test_case --) {
  80.         read();
  81.         process();
  82.     }
  83.     return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 17688KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/tqhIaQ
language:
C++14 (gcc 8.3)
created:
10 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!