Submission #693893

#	Time	Username	Problem	Language	Result	Execution time	Memory
693893		lto5	Plahte (COCI17_plahte)	C++14	0 / 160	308 ms	112692 KiB

plahte

#include <bits/stdc++.h>

using namespace std;
#define int int64_t
#define x1 _x1_
#define x2 _x2_
#define y1 _y1_
#define y2 _y2_

const int N = 1e6 + 5;
const int OPEN = 0;
const int CLOSE = 1;

struct Data {
  int x;
  bool type;
  int id;

  Data(int a = 0, bool t = 0, int i = 0) {
    x = a;
    type = t;
    id = i;
  }

  bool operator<(const Data& rhs) const {
    if (x != rhs.x)
      return x < rhs.x;
    return type < rhs.type;
  }
};

struct Rect {
  int x, y, u, v;
  int64_t area;
  Rect(int _x = 0, int _y = 0, int _u = 0, int _v = 0) {
    x = _x, y = _y, u = _u, v = _v;
    area = 1ll * (u - x) * (v - y);
  }
  void read() {
    cin >> x >> y >> u >> v;
    area = 1ll * (u - x) * (v - y);
  }
  void print() {
    cerr << x << " " << y << " " << u << " " << v;
  }
  bool operator<(const Rect& rhs) const {
    return area > rhs.area;
  }

  bool inside(const pair<int, int>& p) const {
    int px = p.first, py = p.second;
    return x <= px && px <= u && y <= py && py <= v;
  }

  bool inside(const Rect& other) const {
    return other.inside(make_pair(x, y)) && other.inside(make_pair(u, v));
  }
};

vector<int> g[N];
int h[N];
int child[N];
int color[N];
int ans[N];
set<int> s[N];

void dfs(int u, int par = -1) {
  if (color[u]) s[u] = {color[u]};
  for (int v : g[u]) {
    if (v == par) {
      continue;
    }
    dfs(v, u);
    if (s[u].size() < s[v].size()) {
      s[u].swap(s[v]);
    }
    for (int c : s[v]) s[u].insert(c);
  }
//  cerr << u << ": ";
//  for (int c : s[u]) {
//    cerr << c << ", ";
//  }
//  cerr << "\n ans = " << s[u].size();
//  cerr << "\n-----\n";
  ans[u] = s[u].size();
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

//  freopen("bangiay.inp", "r", stdin);
//  freopen("bangiay.out", "w", stdout);

  int n, m;
  cin >> n >> m;

  vector<Data> rect;
  vector<Rect> org_rect(n + m + 1);

  org_rect[0] = Rect(-1e9, -1e9, 1e9, 1e9);

  auto add_rect = [&](int x1, int y1, int x2, int y2, int id) {
    org_rect[id] = Rect(x1, y1, x2, y2);
    rect.emplace_back(x1, OPEN, id);
    rect.emplace_back(x2 + 1, CLOSE, id);
  };

  for (int i = 1; i <= n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    org_rect[i] = {x1, y1, x2, y2};
    add_rect(x1, y1, x2, y2, i);
  }

  vector<int> par(n + 2 * m + 1, 0);

  for (int i = 1; i <= m; i++) {
    int x1, y1;
    cin >> x1 >> y1 >> color[n + i];
    add_rect(x1, y1, x1, y1, n + i);
  }

  sort(rect.begin(), rect.end());
  set<pair<int, int>> coor;

  auto update = [&](int id, int cur_id) {
    if (org_rect[id].inside(org_rect[cur_id])) {
      if (org_rect[par[id]].area > org_rect[cur_id].area) {
        par[id] = cur_id;
      }
    }
  };

  for (auto node : rect) {
    int x = node.x, type = node.type, id = node.id;
    int x1 = org_rect[id].x, y1 = org_rect[id].y, x2 = org_rect[id].u, y2 = org_rect[id].v;
    if (type == CLOSE) {
      coor.erase({y1, id});
      coor.erase({y2, id});
    } else {
      auto it = coor.upper_bound({y1, id});
      if (it != coor.end()) {
        int cur_id = it->second;
        update(id, cur_id);
        update(id, par[cur_id]);
      }
      if (it != coor.begin()) {
        --it;
        int cur_id = it->second;
        update(id, cur_id);
        update(id, par[cur_id]);
      }
      it = coor.upper_bound({y2, id});
      if (it != coor.end()) {
        int cur_id = it->second;
        update(id, cur_id);
        update(id, par[cur_id]);
      }
      if (it != coor.begin()) {
        --it;
        int cur_id = it->second;
        update(id, cur_id);
        update(id, par[cur_id]);
      }

      if (id <= n) {
        coor.insert({y1, id});
        coor.insert({y2, id});
      }
    }
  }

  h[0] = 1;
  for (int i = 1; i <= n + m; i++)
    g[par[i]].push_back(i);
  dfs(0);

  for (int i = 1; i <= n; i++) {
    cout << ans[i] << "\n";
  }

  return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'int32_t main()':
plahte.cpp:137:9: warning: unused variable 'x' [-Wunused-variable]
  137 |     int x = node.x, type = node.type, id = node.id;
      |         ^
plahte.cpp:5:12: warning: unused variable '_x1_' [-Wunused-variable]
    5 | #define x1 _x1_
      |            ^~~~
plahte.cpp:138:9: note: in expansion of macro 'x1'
  138 |     int x1 = org_rect[id].x, y1 = org_rect[id].y, x2 = org_rect[id].u, y2 = org_rect[id].v;
      |         ^~
plahte.cpp:6:12: warning: unused variable '_x2_' [-Wunused-variable]
    6 | #define x2 _x2_
      |            ^~~~
plahte.cpp:138:51: note: in expansion of macro 'x2'
  138 |     int x1 = org_rect[id].x, y1 = org_rect[id].y, x2 = org_rect[id].u, y2 = org_rect[id].v;
      |                                                   ^~

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