SHARE
TWEET

B - Nicoleta's Cleaning

a guest Aug 23rd, 2017 196 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define mp make_pair
  4. #define pb push_back
  5. #define fi first
  6. #define se second
  7. #define N 400001
  8.  
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12. typedef pair<int ,int> ii;
  13. typedef vector<int> vi;
  14.  
  15. int b[N];
  16.  
  17. void update(int pos, int val) {
  18.     while(pos < N) {
  19.         b[pos] += val;
  20.         pos += pos&-pos;
  21.     }
  22. }
  23.  
  24. int query(int pos) {
  25.     int res = 0;
  26.     while(pos) {
  27.         res += b[pos];
  28.         pos -= pos&-pos;
  29.     }
  30.     return res;
  31. }
  32.  
  33. vector<int> ys;
  34. vector<pair<int, pair<int, int> > > ev;
  35. vector<int> p;
  36. vector<pair<int, int> > r;
  37. int ans[100001];
  38.  
  39. int main() {
  40.     int n, m;
  41.     cin >> n >> m;
  42.     for(int i = 0; i < n; i++) {
  43.         int x, y;
  44.         cin >> x >> y; 
  45.         ys.pb(y);
  46.         p.pb(y);
  47.         ev.pb(mp(x, mp(1, i)));
  48.     }
  49.  
  50.     for(int i = 0; i < m; i++) {
  51.         int x1, y1, x2, y2;
  52.         cin >> x1 >> y1 >> x2 >> y2;
  53.         ys.pb(y1);
  54.         ys.pb(y2);
  55.         r.pb(mp(y1, y2));
  56.         ev.pb(mp(x1, mp(2, i)));
  57.         ev.pb(mp(x2, mp(0, i)));
  58.     }
  59.  
  60.     sort(ys.begin(), ys.end());
  61.     ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
  62.     for(int i = 0; i < p.size(); i++) {
  63.         p[i] = lower_bound(ys.begin(), ys.end(), p[i]) - ys.begin() + 1;
  64.     }
  65.     for(int i = 0; i < r.size(); i++) {
  66.         r[i].fi = lower_bound(ys.begin(), ys.end(), r[i].fi) - ys.begin() + 1;
  67.         r[i].se = lower_bound(ys.begin(), ys.end(), r[i].se) - ys.begin() + 1;
  68.     }
  69.  
  70.     sort(ev.begin(), ev.end());
  71.     for(int i = 0; i < ev.size(); i++) {
  72.         int idx = ev[i].se.se;
  73.         if(ev[i].se.fi == 0) {
  74.             if(r[idx].fi != r[idx].se - 1) {
  75.                 update(r[idx].fi + 1, -1);
  76.                 update(r[idx].se, 1);
  77.             }
  78.         } else if(ev[i].se.fi == 1) {
  79.             ans[idx] = query(p[idx]);
  80.         } else {
  81.             if(r[idx].fi != r[idx].se - 1) {
  82.                 update(r[idx].fi + 1, 1);
  83.                 update(r[idx].se, -1);
  84.             }
  85.         }
  86.     }
  87.  
  88.     for(int i = 0; i < n; i++) {
  89.         cout << ans[i] << " \n"[i == n-1];
  90.     }
  91.  
  92.     return 0;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top