제출 #1306889

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306889		chrisvilches	Plahte (COCI17_plahte)	C++20	160 / 160	261 ms	24920 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, points;
    vector<tuple<int, int, int, int>> rectangles;

    for (int i = 0; i < n; i++) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      rectangles.emplace_back(x1, y1, x2, 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(x, 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);

    for (const auto& [x, type, i] : events) {
      if (type != 1) {
        const auto [_, y1, __, y2] = rectangles[i];

        if (type == 2) {
          active.erase(y2);
          continue;
        }

        const auto it = active.lower_bound(y2);
        if (it != active.end()) {
          int idx = it->second;
          assert(idx >= 0);

          while (true) {
            const int parent_y1 = get<1>(rectangles[idx]);

            if (parent_y1 <= y1) {
              parent[i] = idx;
              break;
            }

            idx = parent[idx];
            if (idx == -1) break;
          }
        }
        active[y2] = i;
      } else {
        const auto [_, y, color] = points[i];
        const auto it = active.lower_bound(y);
        if (it == active.end()) continue;

        int idx = it->second;

        while (true) {
          const int y1 = get<1>(rectangles[idx]);

          if (y1 <= y) {
            values[idx].emplace(color);
            break;
          }

          idx = parent[idx];
          if (idx == -1) break;
        }
      }
    }

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

    for (int i = 0; i < n; i++) {
      if (parent[i] != -1) {
        graph[parent[i]].push_back(i);
      }
    }

    vector<int> res(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);
        }
      }

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

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

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

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