제출 #1306890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306890		chrisvilches	Plahte (COCI17_plahte)	C++20	160 / 160	333 ms	23480 KiB

plahte

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m;
  while (cin >> n >> m) {
    vector<tuple<int, int, int>> events;
    vector<pair<int, int>> points, rectangles;

    for (int i = 0; i < n; i++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      rectangles.emplace_back(y1, y2);
      events.emplace_back(x1, 0, i);
      events.emplace_back(x2, 2, i);
    }

    for (int i = 0; i < m; i++) {
      int x, y, color;
      cin >> x >> y >> color;
      points.emplace_back(y, color);
      events.emplace_back(x, 1, i);
    }

    sort(events.begin(), events.end());

    vector<set<int>> values(n);

    map<int, int> active;
    vector<int> parent(n, -1);

    const auto find_rectangle_idx = [&](const int y1, const int y2) {
      const auto it = active.lower_bound(y2);
      if (it == active.end()) return -1;

      int idx = it->second;

      while (idx != -1 && rectangles[idx].first > y1) {
        idx = parent[idx];
      }

      return idx;
    };

    vector<vector<int>> graph(n);

    for (const auto& [x, type, i] : events) {
      if (type == 1) {
        const auto [y, color] = points[i];
        const int idx = find_rectangle_idx(y, y);

        if (idx != -1) {
          values[idx].emplace(color);
        }
        continue;
      }

      const auto [y1, y2] = rectangles[i];

      if (type == 0) {
        const int idx = find_rectangle_idx(y1, y2);
        parent[i] = idx;

        if (idx != -1) {
          graph[idx].emplace_back(i);
        }
        active[y2] = i;
      } else {
        active.erase(y2);
      }
    }

    vector<int> ans(n);

    const function<void(int)> dfs = [&](const int u) {
      for (const int v : graph[u]) dfs(v);

      for (const int v : graph[u]) {
        if (values[u].size() < values[v].size()) {
          values[u].swap(values[v]);
        }

        for (const int c : values[v]) {
          values[u].emplace(c);
        }
      }

      ans[u] = values[u].size();
    };

    for (int i = 0; i < n; i++) {
      if (parent[i] == -1) dfs(i);
    }

    for (const auto& x : ans) {
      cout << x << endl;
    }
  }
}

• Subtask 1: 32 / 32
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32
• Subtask 5: 32 / 32