fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Rect {
  5.     long long A, B, C, D;
  6. };
  7.  
  8. struct Shot {
  9.     long long x, y, col;
  10. };
  11.  
  12. struct Event {
  13.     long long x;
  14.     int type; // 0=open, 1=query, 2=close
  15.     int id;
  16.     bool operator < (const Event& other) const {
  17.         if (x != other.x) return x < other.x;
  18.         return type < other.type;
  19.     }
  20. };
  21.  
  22. struct Edge {
  23.     long long y;
  24.     int type; // 0=bottom, 1=top
  25.     int id;
  26.  
  27.     bool operator < (const Edge& other) const {
  28.         if (y != other.y) return y < other.y;
  29.         if (type != other.type) return type < other.type;
  30.         return id < other.id;
  31.     }
  32. };
  33.  
  34. int main() {
  35.     ios::sync_with_stdio(false);
  36.     cin.tie(nullptr);
  37.  
  38.     int N, M;
  39.     cin >> N >> M;
  40.  
  41.     vector<Rect> rect(N + 1);
  42.     for (int i = 1; i <= N; i++) {
  43.         cin >> rect[i].A >> rect[i].B >> rect[i].C >> rect[i].D;
  44.     }
  45.  
  46.     vector<Shot> shot(M + 1);
  47.     vector<long long> allColors;
  48.  
  49.     for (int i = 1; i <= M; i++) {
  50.         cin >> shot[i].x >> shot[i].y >> shot[i].col;
  51.         allColors.push_back(shot[i].col);
  52.     }
  53.  
  54.     sort(allColors.begin(), allColors.end());
  55.     allColors.erase(unique(allColors.begin(), allColors.end()), allColors.end());
  56.  
  57.     vector<Event> events;
  58.     events.reserve(2 * N + M);
  59.  
  60.     for (int i = 1; i <= N; i++) {
  61.         events.push_back({rect[i].A, 0, i});
  62.         events.push_back({rect[i].C, 2, i});
  63.     }
  64.  
  65.     for (int i = 1; i <= M; i++) {
  66.         events.push_back({shot[i].x, 1, i});
  67.     }
  68.  
  69.     sort(events.begin(), events.end());
  70.  
  71.     vector<int> parent(N + 1, 0);
  72.     vector<int> hitSheet(M + 1, 0);
  73.  
  74.     set<Edge> active;
  75.  
  76.     for (auto &e : events) {
  77.         if (e.type == 0) {
  78.             int id = e.id;
  79.  
  80.             auto it = active.lower_bound({rect[id].B, 1, -1});
  81.  
  82.             if (it != active.end() && it->type == 1)
  83.                 parent[id] = it->id;
  84.             else
  85.                 parent[id] = 0;
  86.  
  87.             active.insert({rect[id].B, 0, id});
  88.             active.insert({rect[id].D, 1, id});
  89.         }
  90.         else if (e.type == 1) {
  91.             int id = e.id;
  92.  
  93.             auto it = active.lower_bound({shot[id].y, 1, -1});
  94.  
  95.             if (it != active.end() && it->type == 1)
  96.                 hitSheet[id] = it->id;
  97.             else
  98.                 hitSheet[id] = 0;
  99.         }
  100.         else {
  101.             int id = e.id;
  102.             active.erase({rect[id].B, 0, id});
  103.             active.erase({rect[id].D, 1, id});
  104.         }
  105.     }
  106.  
  107.     vector<vector<int>> g(N + 1);
  108.     for (int i = 1; i <= N; i++) {
  109.         g[parent[i]].push_back(i);
  110.     }
  111.  
  112.     vector<pair<int,int>> occ;
  113.     occ.reserve(M);
  114.  
  115.     for (int i = 1; i <= M; i++) {
  116.         int u = hitSheet[i];
  117.         if (u == 0) continue;
  118.  
  119.         int c = lower_bound(allColors.begin(), allColors.end(),
  120.                             shot[i].col) - allColors.begin();
  121.  
  122.         occ.push_back({u, c});
  123.     }
  124.  
  125.     sort(occ.begin(), occ.end());
  126.     occ.erase(unique(occ.begin(), occ.end()), occ.end());
  127.  
  128.     vector<vector<int>> nodeColors(N + 1);
  129.     for (auto &p : occ) {
  130.         nodeColors[p.first].push_back(p.second);
  131.     }
  132.  
  133.     vector<int> order;
  134.     order.reserve(N + 1);
  135.  
  136.     vector<int> st;
  137.     st.push_back(0);
  138.  
  139.     while (!st.empty()) {
  140.         int u = st.back();
  141.         st.pop_back();
  142.  
  143.         order.push_back(u);
  144.  
  145.         for (int v : g[u]) st.push_back(v);
  146.     }
  147.  
  148.     vector<unordered_set<int>*> bag(N + 1, nullptr);
  149.     vector<long long> ans(N + 1, 0);
  150.  
  151.     for (int i = (int)order.size() - 1; i >= 0; i--) {
  152.         int u = order[i];
  153.  
  154.         auto *cur = new unordered_set<int>();
  155.  
  156.         for (int c : nodeColors[u]) cur->insert(c);
  157.  
  158.         for (int v : g[u]) {
  159.             auto *child = bag[v];
  160.  
  161.             if (cur->size() < child->size())
  162.                 swap(cur, child);
  163.  
  164.             for (int x : *child)
  165.                 cur->insert(x);
  166.  
  167.             delete child;
  168.         }
  169.  
  170.         bag[u] = cur;
  171.         ans[u] = (long long)cur->size();
  172.     }
  173.  
  174.     for (int i = 1; i <= N; i++) {
  175.         cout << ans[i] << '\n';
  176.     }
  177.  
  178.     delete bag[0];
  179.     return 0;
  180. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UQcFG6
language:
C++14 (gcc 8.3)
created:
13 hours 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!