oj.uz

Submission #693943

# Submission time Handle Problem Language Result Execution time Memory
693943 2023-02-03T12:33:39 Z lto5 Plahte (COCI17_plahte) C++14
160 / 160
 308 ms 51548 KB 
#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 OPEN = 1;
const int CLOSE = -1;
const int QUERY = 0;
const int N = 2e5 + 5;
const int INF = 1e9 + 7;

struct Rect {
  int x1, y1, x2, y2;
  Rect(int a = 0, int b = 0, int c = 0, int d = 0) {
    x1 = a;
    y1 = b;
    x2 = c;
    y2 = d;
  }
  int64_t area() {
    return 1ll * (x2 - x1) * (y2 - y1);
  }
  bool outside(int x, int y) {
    return x1 <= x && x <= x2 && y1 <= y && y <= y2;
  }
  bool outside(const Rect &other) {
    return outside(other.x1, other.y1) && outside(other.x2, other.y2);
  }
} rect[N];

struct Element {
  int x, y, id;
  Element(int xx = 0, int yy = 0, int ii = 0) {
    x = xx;
    y = yy;
    id = ii;
  }
  bool operator<(const Element &e) const {
    if (x != e.x)
      return x < e.x;
    return id > e.id;
  }
};

int n, q;
int par[N];
int color[N];
int ans[N];
vector<int> g[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);
  }
  ans[u] = s[u].size();
}


void solve() {
  cin >> n >> q;
  rect[0] = Rect(0, 0, INF, INF);
  for (int i = 1; i <= n; i++) {
    cin >> rect[i].x1 >> rect[i].y1 >> rect[i].x2 >> rect[i].y2;
  }
  for (int i = n + 1; i <= n + q; i++) {
    int x, y;
    cin >> x >> y >> color[i];
    rect[i] = Rect(x, y, x, y);
  }

  vector<Element> pts;
  auto add_rect = [&](int id) {
    auto [x1, y1, x2, y2] = rect[id];
    pts.emplace_back(x1, id <= n ? OPEN : QUERY, id);
    pts.emplace_back(x2 + 1, id <= n ? CLOSE : QUERY, id);
  };

  for (int i = 0; i <= n + q; i++) {
    add_rect(i);
  }

  memset(par, 0, sizeof(par));

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

  auto upd = [&](int id, int nid) {
    if (rect[nid].outside(rect[id])) {
      int &p = par[id];
      if (rect[p].area() > rect[nid].area())
        p = nid;
    }
  };

  for (auto [x, type, id] : pts) {
    auto [x1, y1, x2, y2] = rect[id];
    if (type == CLOSE) {
      coor.erase({y1, id});
      coor.erase({y2, id});
      continue;
    }

    auto it = coor.upper_bound({y1, id});
    if (it != coor.end()) {
      int cur_id = it->second;
      upd(id, cur_id);
      upd(id, par[cur_id]);
    }
    if (it != coor.begin()) {
      --it;
      int cur_id = it->second;
      upd(id, cur_id);
      upd(id, par[cur_id]);
    }
    it = coor.upper_bound({y2, id});
    if (it != coor.end()) {
      int cur_id = it->second;
      upd(id, cur_id);
      upd(id, par[cur_id]);
    }
    if (it != coor.begin()) {
      --it;
      int cur_id = it->second;
      upd(id, cur_id);
      upd(id, par[cur_id]);
    }

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

  for (int i = 1; i <= n + q; i++) {
    g[par[i]].push_back(i);
  }
  dfs(0);


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

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

Compilation message

plahte.cpp: In lambda function:
plahte.cpp:86:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |     auto [x1, y1, x2, y2] = rect[id];
      |          ^
plahte.cpp: In function 'void solve()':
plahte.cpp:108:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  108 |   for (auto [x, type, id] : pts) {
      |             ^
plahte.cpp:109:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |     auto [x1, y1, x2, y2] = rect[id];
      |          ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 30624 KB Output is correct
2 Correct 90 ms 32484 KB Output is correct
3 Correct 12 ms 22220 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 32120 KB Output is correct
2 Correct 103 ms 32672 KB Output is correct
3 Correct 11 ms 22220 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 40428 KB Output is correct
2 Correct 160 ms 38756 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 51548 KB Output is correct
2 Correct 277 ms 49116 KB Output is correct
3 Correct 11 ms 22240 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 48316 KB Output is correct
2 Correct 285 ms 48872 KB Output is correct
3 Correct 12 ms 22228 KB Output is correct