fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_N = 300000;
  5.  
  6. int n;
  7. struct Buffalo {
  8.     int x, y;
  9. } b[MAX_N];
  10.  
  11. int m;
  12. struct Settler {
  13.     int x, y;
  14.     int x_fence = 0;
  15.     int y_fence = 0;
  16.     int buffalos_start = 0;
  17.     int buffalos_end = 0;
  18.     int parent_end = -1;
  19. } s[MAX_N];
  20.  
  21. struct Group {
  22.     Group* parent = nullptr;
  23.     int rank = 0;
  24.     int buffalos = 0;
  25. } group[MAX_N];
  26.  
  27.  
  28. struct Vertical {
  29.     int x, index;
  30. };
  31.  
  32. bool operator<(const Vertical& a, const Vertical& b) {
  33.     return a.x != b.x ? a.x < b.x : a.index < b.index;
  34. }
  35.  
  36. struct Event {
  37.     int y, index;
  38.     enum Type { FENCE_POST = 1,
  39.                 BUFFALO = 2 } type;
  40. };
  41.  
  42. bool operator<(const Event& a, const Event& b) {
  43.     return a.y != b.y ? a.y > b.y : a.type < b.type;
  44. }
  45.  
  46. void Sweep() {
  47.     set<Vertical> active;
  48.     vector<Event> events;
  49.     events.reserve(n + m);
  50.     for (int i = 0; i < n; ++i) {
  51.         events.push_back(Event{b[i].y, i, Event::BUFFALO});
  52.     }
  53.     for (int i = 0; i < m; ++i) {
  54.         events.push_back(Event{s[i].y, i, Event::FENCE_POST});
  55.     }
  56.     sort(events.begin(), events.end());
  57.     for (const Event& e : events) {
  58.         if (e.type == Event::FENCE_POST) {
  59.             const auto it = active.insert(Vertical{s[e.index].x, e.index}).first;
  60.             auto next = it;
  61.             if (++next != active.end()) {
  62.                 s[e.index].parent_end = next->index;
  63.             }
  64.  
  65.             auto curr = it;
  66.             auto prev = curr;
  67.             while (prev != active.begin()) {
  68.                 --prev;
  69.                 if (prev->index < e.index) {
  70.                     break;
  71.                 }
  72.                 s[prev->index].y_fence = e.y;
  73.                 curr = prev;
  74.             }
  75.             if (prev != curr) {
  76.                 s[e.index].x_fence = prev->x;
  77.             }
  78.             active.erase(curr, it);
  79.         } else {
  80.             const auto it = active.lower_bound(Vertical{b[e.index].x, -1});
  81.             if (it != active.end()) {
  82.                 ++s[it->index].buffalos_end;
  83.             }
  84.         }
  85.     }
  86. }
  87.  
  88. Group* Find(Group* a) {
  89.     if (a->parent == nullptr) {
  90.         return a;
  91.     }
  92.     return a->parent = Find(a->parent);
  93. }
  94.  
  95. Group* Union(Group* a, Group* b) {
  96.     if (a->rank < b->rank) {
  97.         swap(a, b);
  98.     }
  99.     if (a->rank == b->rank) {
  100.         ++a->rank;
  101.     }
  102.     b->parent = a;
  103.     a->buffalos += b->buffalos;
  104.     return a;
  105. }
  106.  
  107. int main() {
  108.     ios::sync_with_stdio(0);
  109.     cin.tie(0);
  110.     cout.tie(0);
  111.  
  112.     freopen("COWBOY.inp", "r", stdin);
  113.     freopen("COWBOY.out", "w", stdout);
  114.  
  115.     cin >> n;
  116.     for (int i = 0; i < n; ++i) {
  117.         cin >> b[i].x >> b[i].y;
  118.     }
  119.     cin >> m;
  120.     for (int i = 0; i < m; ++i) {
  121.         cin >> s[i].x >> s[i].y;
  122.     }
  123.  
  124.     Sweep();
  125.     for (int i = m - 1; i >= 0; --i) {
  126.         Group* g = Find(&group[i]);
  127.         g->buffalos += s[i].buffalos_end;
  128.         s[i].buffalos_start = g->buffalos;
  129.         if (s[i].parent_end != -1) {
  130.             Group* p = Find(&group[s[i].parent_end]);
  131.             Union(g, p);
  132.         }
  133.     }
  134.     for (int i = 0; i < m; ++i) {
  135.         cout << s[i].buffalos_start << '\n';
  136.     }
  137.     return 0;
  138. }
  139.  
Success #stdin #stdout 0.01s 14164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/95su4A
language:
C++14 (gcc 8.3)
created:
5 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!