oj.uz

Submission #701458

# Submission time Handle Problem Language Result Execution time Memory
701458 2023-02-21T09:06:14 Z mgl_diamond Plahte (COCI17_plahte) C++14
160 / 160
 341 ms 49912 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

#define FOR(i, l, r) for(int i=(l); i<=(r); ++i)
#define FORD(i, l, r) for(int i=(l); i>=(r); --i)
#define FORE(x, v) for(auto &x : v)
#define vec vector
#define fi first
#define se second
#define ins push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define lc id<<1
#define rc id<<1|1
#define file "input"

const int nx = 80000+5;

// tournament tree
bool touch[nx * 12];
int sgt[nx * 12];

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

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

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

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, c;
  ball(int _u=0, int _v=0, int _c=0) : u(_u), v(_v), c(_c) {}
};

int n, m;
rect a[nx];
ball balls[nx];
vec<pii> point[nx * 3];
vec<int> stEdge[nx * 3], enEdge[nx * 3];
vec<int> dx, dy;

int ans[nx], pa[nx];
vec<int> graph[nx];
set<int> bag[nx];

int pos(int x, vec<int> &v) {
  return upper_bound(all(v), x) - v.begin();
}

void dfs(int u) {
  FORE(v, graph[u]) {
    dfs(v);
    if (bag[u].size() < bag[v].size()) swap(bag[u], bag[v]);
    for(int x : bag[v]) bag[u].insert(x);
  }
  ans[u] = bag[u].size();
}

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

  FOR(i, 1, n) {
    int u, v, p, q;
    cin >> u >> v >> p >> q;
    a[i] = rect(u, v, p, q);
    dx.ins(a[i].u); dx.ins(a[i].p);
    dy.ins(a[i].v); dy.ins(a[i].q);
  }

  FOR(i, 1, m) {
    int u, v, c;
    cin >> u >> v >> c;
    balls[i] = ball(u, v, c);
    dx.ins(u); dy.ins(v);
  }

  sort(all(dx)); dx.resize(unique(all(dx)) - dx.begin());
  sort(all(dy)); dy.resize(unique(all(dy)) - dy.begin());
//
  FOR(i, 1, n) {
    a[i].u = pos(a[i].u, dx); a[i].v = pos(a[i].v, dy);
    a[i].p = pos(a[i].p, dx); a[i].q = pos(a[i].q, dy);
    int u = a[i].u, p = a[i].p;
    stEdge[u].ins(i); enEdge[p].ins(i);
  }

  FOR(i, 1, m) {
    int u = balls[i].u, v = balls[i].v, c = balls[i].c;
    u = pos(u, dx); v = pos(v, dy);
    point[u].ins({v, c});
  }

  int init = m;
  m = sz(dy);
  FOR(i, 1, sz(dx)) {
    FORE(x, stEdge[i]) {
      int l = a[x].v, r = a[x].q;
      pa[x] = query(1, 1, m, l);
      graph[pa[x]].ins(x);
      upd(1, 1, m, l, r, x);
    }

    FORE(x, point[i]) {
      int tmp = query(1, 1, m, x.fi);
      bag[tmp].insert(x.se);
    }

    FORE(x, enEdge[i]) {
      int l = a[x].v, r = a[x].q;
      upd(1, 1, m, l, r, pa[x]);
    }
  }

  dfs(0);
  FOR(i, 1, n) cout << ans[i] << "\n";
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }

  int t = 1;
  while (t--) solve();
  return 0;
}

Compilation message

plahte.cpp: In function 'void solve()':
plahte.cpp:121:7: warning: unused variable 'init' [-Wunused-variable]
  121 |   int init = m;
      |       ^~~~
plahte.cpp: In function 'int main()':
plahte.cpp:151:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:152:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 32160 KB Output is correct
2 Correct 101 ms 32724 KB Output is correct
3 Correct 14 ms 25044 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 33928 KB Output is correct
2 Correct 122 ms 33028 KB Output is correct
3 Correct 12 ms 25044 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 41604 KB Output is correct
2 Correct 190 ms 36604 KB Output is correct
3 Correct 12 ms 25080 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 49912 KB Output is correct
2 Correct 338 ms 45216 KB Output is correct
3 Correct 14 ms 25044 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 47916 KB Output is correct
2 Correct 308 ms 43804 KB Output is correct
3 Correct 12 ms 25044 KB Output is correct