QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#606457#6308. Magicnhuang685WA 21ms5456kbC++237.0kb2024-10-03 08:53:472024-10-03 08:53:47

Judging History

你现在查看的是最新测评结果

  • [2024-10-03 08:53:47]
  • 评测
  • 测评结果:WA
  • 用时:21ms
  • 内存:5456kb
  • [2024-10-03 08:53:47]
  • 提交

answer

/**
 * @author n685
 * @brief
 * @date 2024-10-02 17:47:12
 *
 *
 */
#include <utility>

#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

struct Node {
  std::array<int, 2> ch{-1, -1};
};
struct Seg {
  int sz{};
  std::vector<Node> data;
  std::vector<int> rts;
  Seg() = default;
  explicit Seg(int sz_, int nrts)
      : sz{static_cast<int>(std::bit_ceil<uint32_t>(sz_))},
        rts(nrts, -1) {}
  int copy_node(int ind) {
    if (ind == -1) {
      data.emplace_back();
    } else {
      data.push_back(data[ind]);
    }
    return static_cast<int>(data.size()) - 1;
  }
  void nch(int node, int ch) {
    int ind = copy_node(data[node].ch[ch]);
    data[node].ch[ch] = ind;
  }
  void upd(int i, int node, int l, int r) {
    if (l == r) {
      return;
    }
    int mid = (l + r) / 2;
    if (i <= mid) {
      nch(node, 0);
      upd(i, data[node].ch[0], l, mid);
    } else {
      nch(node, 1);
      upd(i, data[node].ch[1], mid + 1, r);
    }
  }
  void upd(int t, int i) { upd(i, rts[t], 0, sz - 1); }
  bool is_there(int i, int node, int l, int r) {
    if (l == r) {
      return true;
    }
    int mid = (l + r) / 2;
    if (i <= mid) {
      if (data[node].ch[0] == -1) {
        return false;
      }
      return is_there(i, data[node].ch[0], l, mid);
    }
    if (data[node].ch[1] == -1) {
      return false;
    }
    return is_there(i, data[node].ch[1], mid + 1, r);
  }
  bool is_there(int t, int i) { return is_there(i, rts[t], 0, sz - 1); }
  void new_rt(int ind) { rts[ind] = copy_node(-1); }
  void copy_rt(int rc, int ind) { rts[rc] = copy_node(rts[ind]); }
#ifdef LOCAL
  void debug(std::vector<int> &s, int ll, int rr, int node, int l, int r) {
    if (l == r) {
      s.push_back(l);
    }
    int mid = (l + r) / 2;
    if (data[node].ch[0] != -1 && ll <= mid) {
      debug(s, ll, rr, data[node].ch[0], l, mid);
    }
    if (data[node].ch[1] != -1 && rr > mid) {
      debug(s, ll, rr, data[node].ch[1], mid + 1, r);
    }
  }
  std::vector<int> debug(int t, int ll, int rr) {
    std::vector<int> ans;
    debug(ans, ll, rr, rts[t], 0, sz - 1);
    return ans;
  }
#else
  std::string debug(int t) { return ""; }
#endif
};

struct II {
  int l, r;
};

struct Flow {
  int sz, s = -1, t = -1;
  std::vector<bool> vis;
  Seg &adj;
  std::vector<II> &ii;
  std::vector<int> left;
  std::vector<bool> is_left;
  explicit Flow(
    int _sz,
    Seg &adj_,
    std::vector<II> &ii_,
    std::vector<int> left_
  )
      : sz(_sz),
        vis(sz),
        adj(adj_),
        ii(ii_),
        left(std::move(left_)),
        is_left(sz) {
    for (int i : left) {
      is_left[i] = true;
    }
  }

  std::vector<int> l, h;
  void bfs() {
    l.assign(sz, static_cast<int>(1e9));
    l[s] = 0;
    std::queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int node = q.front();
      q.pop();
      if (node == s) {
        for (int i : left) {
          if (!vis[i] && l[i] > l[node] + 1) {
            l[i] = l[node] + 1;
            q.push(i);
          }
        }
      } else if (is_left[node]) {
        for (int i = ii[node].l; i < ii[node].r; ++i) {
          if (adj.is_there(node, i) && l[i] > l[node] + 1) {
            l[i] = l[node] + 1;
            q.push(i);
          }
        }
      } else if (node != t) {
        if (!vis[node] && l[t] > l[node] + 1) {
          l[t] = l[node] + 1;
        }
        for (int i = ii[node].l; i < ii[node].r; ++i) {
          if (adj.is_there(node, i) && l[i] > l[node] + 1) {
            l[i] = l[node] + 1;
            q.push(i);
          }
        }
      }
      // for (Edge &e : adj[node]) {
      //   if (e.cap > 0 && l[e.v] > l[node] + 1) {
      //     l[e.v] = l[node] + 1;
      //     q.push(e.v);
      //   }
      // }
    }
  }
  int dfs(int node) {
    if (node == t) {
      return 1;
    }
    if (node == s) {
      for (; h[node] < static_cast<int>(left.size()); ++h[node]) {
        int i = left[h[node]];
        if (!vis[i] && l[i] == l[node] + 1) {
          int val = dfs(i);
          if (val > 0) {
            vis[i] = true;
            return 1;
          }
        }
      }
    } else if (is_left[node]) {
      if (h[node] == 0) {
        h[node] = ii[node].l;
      }
      for (; h[node] < ii[node].r; ++h[node]) {
        int i = h[node];
        if (adj.is_there(node, i) && l[i] == l[node] + 1) {
          int val = dfs(i);
          if (val > 0) {
            vis[i] = true;
            return 1;
          }
        }
      }
    } else {
      if (!vis[node] && l[t] == l[node] + 1) {
        vis[node] = true;
        return 1;
      }
      if (h[node] == 0) {
        h[node] = ii[node].l;
      }
      for (; h[node] < ii[node].r; ++h[node]) {
        int i = h[node];
        if (vis[i] && adj.is_there(node, i) && l[i] == l[node] + 1) {
          int val = dfs(i);
          if (val > 0) {
            return 1;
          }
        }
      }
    }
    // for (; h[node] < static_cast<int>(adj[node].size()); ++h[node]) {
    //   Edge &e = adj[node][h[node]];
    //   if (e.cap > 0 && l[e.v] == l[node] + 1) {
    //     T val = dfs(e.v, std::min(f, e.cap));
    //     if (val) {
    //       e.cap -= val;
    //       adj[e.v][e.rev].cap += val;
    //       return val;
    //     }
    //   }
    // }
    return 0;
  }
  int max_flow(int _s, int _t) {
    s = _s;
    t = _t;
    bfs();
    int ans = 0;
    while (l[t] != static_cast<int>(1e9)) {
      h.assign(sz, 0);
      // ans += dfs(s, std::numeric_limits<T>::max());
      while (int res = dfs(s)) {
        ans += res;
      }
      bfs();
    }
    return ans;
  }
};

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif
  start_clock();

  int n;
  std::cin >> n;

  std::vector<II> ii(n);
  std::vector<II> both(2 * n);
  std::vector<int> left;
  for (auto &[l, r] : ii) {
    std::cin >> l >> r;
    --l;
    --r;
    left.push_back(l);
  }
  rs::sort(ii, {}, &II::l);
  for (int i = 0; i < n; ++i) {
    both[ii[i].l] = ii[i];
    both[ii[i].r] = ii[i];
  }

  Seg adj(2 * n, 2 * n);
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      adj.new_rt(ii[i].l);
    } else {
      adj.copy_rt(ii[i].l, ii[i - 1].l);
    }
    if (i > 0) {
      adj.upd(ii[i].l, ii[i - 1].r);
    }
  }
  rs::sort(ii, {}, &II::r);
  for (int i = n - 1; i >= 0; --i) {
    if (i == n - 1) {
      adj.new_rt(ii[i].r);
    } else {
      adj.copy_rt(ii[i].r, ii[i + 1].r);
    }
    if (i < n - 1) {
      adj.upd(ii[i].r, ii[i + 1].l);
    }
  }
  const int s = 2 * n, t = 2 * n + 1;
  Flow flow(2 * n + 2, adj, both, left);
  std::cout << 2 * n - flow.max_flow(s, t) << '\n';
  end_clock();
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3616kb

input:

5
2 3
6 7
1 9
5 10
4 8

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 4ms
memory: 5456kb

input:

5000
7985 7987
42 46
1591 1593
407 410
6305 6306
1456 1457
5874 5875
7135 7137
7041 7046
6813 6815
8868 8871
665 666
4055 4056
9789 9796
7067 7068
4745 4746
5167 5171
1735 1737
2125 2128
1444 1447
1348 1352
6087 6090
1381 1384
1600 1601
5187 5190
2801 2802
8449 8450
9376 9377
4021 4024
2674 2676
490...

output:

8134

result:

ok 1 number(s): "8134"

Test #3:

score: -100
Wrong Answer
time: 21ms
memory: 5444kb

input:

5000
3171 3172
4062 4064
4647 4651
3670 3673
7112 7114
9714 9717
3781 3789
8422 8426
457 460
5450 5454
7113 7122
6313 6320
9969 9973
828 832
6878 6892
4476 4483
892 903
251 259
6304 6315
130 134
9206 9215
2679 2686
9090 9091
8222 8228
9374 9375
2985 2989
3397 3401
4916 4918
6819 6821
883 889
2516 25...

output:

6962

result:

wrong answer 1st numbers differ - expected: '7047', found: '6962'