Submission #1014395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014395		MilosMilutinovic	Plahte (COCI17_plahte)	C++14	0 / 160	2087 ms	524288 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n), c(n), d(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      assert(a[i] != a[j] || b[i] != b[j] || c[i] != c[j] || d[i] != d[j]);
    }
  }
  vector<int> x(m), y(m), k(m);
  for (int i = 0; i < m; i++) {
    cin >> x[i] >> y[i] >> k[i];
  }
  vector<array<int, 3>> ev;
  for (int i = 0; i < n; i++) {
    ev.push_back({a[i], i, 0});
    ev.push_back({c[i] + 1, ~i, 1});
  }
  for (int i = 0; i < m; i++) {
    ev.push_back({x[i], n + i, 2});
  }
  sort(ev.begin(), ev.end());
  set<array<int, 3>> st;
  set<array<int, 3>> rst;
  vector<vector<int>> g(n);
  vector<set<int>> col(n);
  for (auto& p : ev) {
    int i = p[1];
    if (p[2] == 0) {
      auto it = st.lower_bound({b[i], -1, -1});
      if (it != st.begin()) {
        it = prev(it);
        if ((*it)[0] < b[i] && (*it)[1] > d[i]) {
          g[(*it)[2]].push_back(i);
        }
      }
      st.insert({b[i], d[i], i});
      rst.insert({d[i], b[i], i});
    }
    if (p[2] == 1) {
      i = ~i;
      st.erase({b[i], d[i], i});
      rst.erase({d[i], b[i], i});
    }
    if (p[2] == 2) {
      i -= n;
      auto it = rst.lower_bound({y[i], -1, -1});
      if (it != rst.end()) {
        if ((*it)[0] >= y[i] && (*it)[1] <= y[i]) {
          col[(*it)[2]].insert(k[i]);
        }
      }
    }
  }
  vector<bool> root(n, true);
  for (int i = 0; i < n; i++) {
    for (int j : g[i]) {
      root[j] = false;
    }
  }
  function<void(int)> Dfs = [&](int v) {
    for (int u : g[v]) {
      Dfs(u);
      for (int c : col[u]) {
        col[v].insert(c);
      }
    }
  };
  for (int i = 0; i < n; i++) {
    if (root[i]) {
      Dfs(i);
    }
  }
  for (int i = 0; i < n; i++) {
    cout << (int) col[i].size() << '\n';
  }
  return 0;
}

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