oj.uz

Submission #674877

# Submission time Handle Problem Language Result Execution time Memory
674877 2022-12-26T12:32:49 Z mgl_diamond Plahte (COCI17_plahte) C++14
160 / 160
 469 ms 203048 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define vec vector
#define ins push_back
#define lc id<<1
#define rc id<<1|1

const int nax = 1e6;

void read(string name="") {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (name.size()) {
    freopen((name + ".inp").c_str(), "r", stdin);
    freopen((name + ".out").c_str(), "w", stdout);
  }
}

struct tournament_tree {
  int n;
  vec<int> sgt, done;

  void init(int _n) {
    n = _n;
    sgt = vec<int>(n*4+1);
    done = vec<int>(n*4+1, 1);
  }

  void app(int id) {
    if (done[id]) return;
    sgt[lc] = sgt[id];
    sgt[rc] = sgt[id];
    done[lc] = done[rc] = 0;
    done[id] = 1;
  }

  void add(int id, int lb, int rb, int l, int r, int val) {
    if (l <= lb && rb <= r) {
      sgt[id] = val;
      done[id] = 0;
      return;
    } else if (rb < l || lb > r)
      return;
    app(id);
    int mb = (lb + rb) >> 1;
    add(lc, lb, mb, l, r, val);
    add(rc, mb+1, rb, l, r, val);
  }

  int query(int id, int lb, int rb, int i) {
    if (lb == rb) return sgt[id];
    // if (i == 2) cout << lb << " " << rb << " " << sgt[id] << "\n";
    app(id);
    int mb = (lb + rb) >> 1;
    if (i <= mb) return query(lc, lb, mb, i);
    return query(rc, mb+1, rb, i);
  }

  void add(int l, int r, int val) {
    add(1, 1, n, l, r, val);
  }

  int query(int i) {
    return query(1, 1, n, i);
  } 
} sgt;

struct event {
  int x, u, v, idx;
  event(int _x=0, int _u=0, int _v=0, int _idx=0) : x(_x), u(_u), v(_v), idx(_idx) {}
  bool operator<(const event b) const {
    if (x == b.x) {
      if (idx < 0) return 0;
      if (b.idx < 0) return 1;
      return v < b.v;
    }
    return x < b.x;
  }
};

struct rect {
  int u, v, p, q;
  rect(int _u=0, int _v=0, int _p=0, int _q=0) : u(_u), v(_v), p(_p), q(_q) {}
};

struct ball {
  int u, v, k;
  ball(int _u=0, int _v=0, int _k=0) : u(_u), v(_v), k(_k) {}
};

int n, m, pa[nax], pb[nax], ans[nax];
rect a[nax];
ball b[nax];
set<int> col[nax];
vec<event> evts;
vec<int> zip, tree[nax];
vec<event> st[nax], en[nax], pts[nax];

// initialize

int pos(int val) {
  return upper_bound(zip.begin(), zip.end(), val) - zip.begin();
}

void input() {
  cin >> n >> m;

  for(int i=1; i<=n; ++i) {
    cin >> a[i].u >> a[i].v >> a[i].p >> a[i].q;
    zip.ins(a[i].u);
    zip.ins(a[i].v);
    zip.ins(a[i].p);
    zip.ins(a[i].q);
  }

  for(int i=1; i<=m; ++i) {
    cin >> b[i].u >> b[i].v >> b[i].k;
    zip.ins(b[i].u);
    zip.ins(b[i].v);
  }

  sort(zip.begin(), zip.end());
  zip.erase(unique(zip.begin(), zip.end()), zip.end());
  sgt.init(zip.size());

  for(int i=1; i<=n; ++i) {
    a[i].u = pos(a[i].u);
    a[i].v = pos(a[i].v);
    a[i].p = pos(a[i].p);
    a[i].q = pos(a[i].q);
  }

  for(int i=1; i<=m; ++i) {
    b[i].u = pos(b[i].u);
    b[i].v = pos(b[i].v);
  }
}

void sweep() {
  for(int i=1; i<=n; ++i) {
    evts.ins(event(a[i].u, a[i].v, a[i].q, i));
    evts.ins(event(a[i].p, a[i].v, a[i].q, -i));
  }

  for(int i=1; i<=m; ++i) {
    evts.ins(event(b[i].u, b[i].v, nax, i));
  }

  sort(evts.begin(), evts.end());
  for(int i=0; i<evts.size(); ++i) {
    auto tmp = evts[i];

    if (tmp.v == nax) {
      pb[tmp.idx] = sgt.query(tmp.u);
      col[pb[tmp.idx]].insert(b[tmp.idx].k);
      continue;
    }

    if (tmp.idx < 0) sgt.add(tmp.u, tmp.v, pa[-tmp.idx]);
    else {
      pa[tmp.idx] = sgt.query(tmp.u);
      tree[pa[tmp.idx]].ins(tmp.idx);
      sgt.add(tmp.u, tmp.v, tmp.idx);
    }
  }
}

void dfs(int u, int p) {
  for(int v : tree[u]) if (v != p) {
    dfs(v, u);
    if (col[u].size() < col[v].size())
      swap(col[u], col[v]);
    for(int x : col[v]) 
      col[u].insert(x);
  }
  ans[u] = col[u].size();
}

void question() {
  dfs(0, 0);
  for(int i=1; i<=n; ++i)
    cout << ans[i] << "\n";
}

int main() {
  read("");
  input();
  sweep();
  question();
  return 0;
}

Compilation message

plahte.cpp: In function 'void sweep()':
plahte.cpp:153:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |   for(int i=0; i<evts.size(); ++i) {
      |                ~^~~~~~~~~~~~
plahte.cpp: In function 'void read(std::string)':
plahte.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen((name + ".inp").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen((name + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 179272 KB Output is correct
2 Correct 175 ms 179980 KB Output is correct
3 Correct 94 ms 168580 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 181624 KB Output is correct
2 Correct 199 ms 181240 KB Output is correct
3 Correct 92 ms 168588 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 190636 KB Output is correct
2 Correct 260 ms 188592 KB Output is correct
3 Correct 85 ms 168616 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 203048 KB Output is correct
2 Correct 469 ms 201836 KB Output is correct
3 Correct 74 ms 168620 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 201148 KB Output is correct
2 Correct 403 ms 199748 KB Output is correct
3 Correct 90 ms 168664 KB Output is correct