Advertisement
Guest User

po, navarro...

a guest
Sep 21st, 2019
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define st first
  5. #define nd second
  6. #define mp make_pair
  7. #define pb push_back
  8. #define cl(x, v) memset((x), (v), sizeof(x))
  9.  
  10. #define db(x) cerr << #x << " == " << x << endl
  11. #define dbs(x) cerr << x << endl
  12. #define _ << ", " <<
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. typedef pair<int, int> pii;
  18. typedef pair<pii, pii> p4i;
  19. typedef pair<int, pii> piii;
  20. typedef pair<ll, ll> pll;
  21. typedef vector<int> vi;
  22.  
  23. const ld EPS = 1e-9, PI = acos(-1.);
  24. const int INF = 0x3f3f3f3f, MOD = 1e9+7;
  25. const int N = 1e5+5, P = 1e6+5;
  26.  
  27. int n, m, x[N], y[N], rx[N][2], ry[N][2], ans[N];
  28. vector<piii> v;
  29. int bit[P];
  30.  
  31. void addp(int p, int v) { for (p+=2; p<P; p+=p&-p) bit[p] += v; }
  32. void add(int l, int r) { addp(l+1, 1); addp(r, -1); }
  33. void rem(int l, int r) { addp(l+1, -1); addp(r, 1); }
  34.  
  35. int query(int p) {
  36.   int sum = 0;
  37.   for (p+=2; p; p-=p&-p) sum += bit[p];
  38.   return sum;
  39. }
  40.  
  41. int main() {
  42.   scanf("%d%d", &n, &m);
  43.   vi cc;
  44.   for (int i = 0; i < n; i++) scanf("%d%d", &x[i], &y[i]), v.pb({ x[i], { 0, i }}), cc.pb(y[i]);
  45.   for (int i = 0; i < m; i++) {
  46.     scanf("%d%d%d%d", &rx[i][0], &ry[i][0], &rx[i][1], &ry[i][1]);
  47.     v.pb({ rx[i][0], { 1, i }});
  48.     v.pb({ rx[i][1], { -1, i }});
  49.     cc.pb(ry[i][0]); cc.pb(ry[i][1]);
  50.   }
  51.   sort(v.begin(), v.end());
  52.  
  53.   sort(cc.begin(), cc.end());
  54.   cc.erase(unique(cc.begin(), cc.end()), cc.end());
  55.   for (int i = 0; i < n; i++) y[i] = lower_bound(cc.begin(), cc.end(), y[i])-cc.begin();
  56.   for (int i = 0; i < m; i++)
  57.     ry[i][0] = lower_bound(cc.begin(), cc.end(), ry[i][0])-cc.begin(),
  58.     ry[i][1] = lower_bound(cc.begin(), cc.end(), ry[i][1])-cc.begin();
  59.  
  60.   for (auto k : v) {
  61.     int i = k.nd.nd;
  62.     //db(k.st _ k.nd.st _ k.nd.nd);
  63.     if (k.nd.st == 0) ans[i] = query(y[i]);
  64.     else if (k.nd.st == -1) rem(ry[i][0], ry[i][1]);
  65.     else add(ry[i][0], ry[i][1]);
  66.   }
  67.  
  68.   for (int i = 0; i < n; i++) printf("%d\n", ans[i]);
  69.  
  70.   return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement