QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232259#7439. 铃原露露nhuang6850 150ms72952kbC++209.9kb2023-10-30 08:51:562023-10-30 08:51:57

Judging History

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

  • [2023-10-30 08:51:57]
  • 评测
  • 测评结果：0
  • 用时：150ms
  • 内存：72952kb
查看
  • [2023-10-30 08:51:56]
  • 提交

answer

/**
 * @file
 * @author n685
 * @brief
 * @date 2023-10-24
 *
 *
 */
#include <bits/stdc++.h>

#ifdef LOCAL
std::ifstream cin;
std::ofstream cout;
using std::cerr;
#else
using std::cin;
using std::cout;
#define cerr                                                                   \
  if (false)                                                                   \
  std::cerr
#endif

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbgR(...) 4242
#define dbgP(...) 420
#define dbgRP(...) 420420
void nline() {}
#endif

template <class Node> struct LSeg {
  using T = typename Node::ValueType;
  using RT = typename Node::RT;
  int h, sz;
  std::vector<Node> val;

  void push(int l, int r) {
    l += sz, r += sz;
    for (int s = h - 1, k = (1 << (h - 1)); s >= 1; --s, k /= 2)
      for (int i = (l >> s); i <= (r >> s); ++i)
        val[i].push(val[2 * i], val[2 * i + 1], k);
  }
  void build(int l, int r) {
    l += sz, r += sz;
    l /= 2, r /= 2;
    for (int k = 2; l >= 1; l /= 2, r /= 2, k *= 2)
      for (int i = l; i <= r; ++i)
        val[i].pull(val[2 * i], val[2 * i + 1]);
  }

  LSeg() {}
  LSeg(int _sz) {
    if (_sz == 1) {
      h = 1;
      sz = 1;
    } else {
      h = std::__lg(_sz - 1) + 2;
      sz = (1 << (h - 1));
    }
    val.resize(2 * sz);
  }
  LSeg(const std::vector<T> &v) : LSeg(static_cast<int>(v.size())) {
    for (int i = 0; i < static_cast<int>(v.size()); ++i)
      val[i + sz] = v[i];
    build(0, sz - 1);
  }

  void upd(int l, int r, const std::function<void(Node &, int)> &f) {
    if (l > r)
      return;
    push(l, l), push(r, r);

    bool cl = false, cr = false;
    int k = 1;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2, k *= 2) {
      if (cl)
        val[l - 1].pull(val[2 * l - 2], val[2 * l - 1]);
      if (cr)
        val[r + 1].pull(val[2 * r + 2], val[2 * r + 3]);
      if (l % 2 == 1)
        f(val[l++], k), cl = true;
      if (r % 2 == 0)
        f(val[r--], k), cr = true;
    }
    for (--l, ++r; r >= 1; l /= 2, r /= 2) {
      if (cl)
        val[l].pull(val[2 * l], val[2 * l + 1]);
      if (cr && (!cl || l != r))
        val[r].pull(val[2 * r], val[2 * r + 1]);
    }
  }
  void set(int l, int r, T v) {
    upd(l, r, [&v](Node &n, int k) { n.set(v, k); });
  }
  void upd(int l, int r) {
    upd(l, r, [](Node &n, int k) { n.upd(k); });
  }
  RT query(int l, int r) {
    if (l > r)
      return Node::ID;
    push(l, l), push(r, r);

    RT ll = Node::ID, rr = Node::ID;
    for (l += sz, r += sz; l <= r; l /= 2, r /= 2) {
      if (l % 2 == 1)
        ll = Node::comb(val[l++], ll);
      if (r % 2 == 0)
        rr = Node::comb(rr, val[r--]);
    }
    return Node::comb(ll, rr);
  }

  int walkL(int l, int r, const std::function<bool(int64_t)> &c) {
    if (l > r)
      return -1;
    push(l, l);
    l += sz;
    if (c(val[l]))
      return l - sz;

    int ind = -1;
    int s = 1;
    for (; l > 1; l /= 2, s *= 2) {
      if (l % 2 == 0 && c(val[l + 1])) {
        ind = l + 1;
        break;
      }
    }
    if (ind == -1)
      return -1;

    while (ind < sz) {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind]))
        ind = 2 * ind;
      else if (c(val[2 * ind + 1]))
        ind = 2 * ind + 1;
      else
        return -1;
      s /= 2;
    }
    if (c(val[ind]) && ind - sz <= r)
      return ind - sz;
    else
      return -1;
  }
  int walkR(int l, int r, const std::function<bool(int64_t)> &c) {
    if (l > r)
      return -1;
    push(r, r);
    r += sz;
    if (c(val[r]))
      return r - sz;

    int ind = -1;
    int s = 1;
    for (; r > 1; r /= 2, s *= 2) {
      if (r % 2 == 1 && c(val[r - 1])) {
        ind = r - 1;
        break;
      }
    }
    if (ind == -1)
      return -1;

    while (ind < sz) {
      val[ind].push(val[2 * ind], val[2 * ind + 1], s);
      if (c(val[2 * ind + 1]))
        ind = 2 * ind + 1;
      else if (c(val[2 * ind]))
        ind = 2 * ind;
      else
        return -1;
      s /= 2;
    }
    if (c(val[ind]) && ind - sz >= l)
      return ind - sz;
    else
      return -1;
  }
};
template <class T> struct NodeMax {
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = (RT)-1e9;
  static constexpr T ID2 = (T)-1e9;
  T val = 0;
  T ls = ID2;
  NodeMax() {}
  NodeMax(T v) : val(v) {}
  operator RT() { return val; }
  static RT comb(RT a, RT b) { return std::max(a, b); }
  void set(T v, [[maybe_unused]] int k) {
    val = std::max(val, v);
    ls = std::max(ls, v);
  }
  void pull(NodeMax &ll, NodeMax &rr) {
    if (ls != ID2)
      return;
    val = std::max(ll.val, rr.val);
  }
  void push(NodeMax &ll, NodeMax &rr, int k) {
    if (ls == ID2) {
      return;
    } else {
      ll.set(ls, k / 2);
      rr.set(ls, k / 2);
    }
    ls = ID2;
  }
};
template <class T> struct NodeMin {
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = (RT)1e9;
  static constexpr T ID2 = (T)1e9;
  T val = 0;
  T ls = ID2;
  NodeMin() {}
  NodeMin(T v) : val(v) {}
  operator RT() { return val; }
  static RT comb(RT a, RT b) { return std::min(a, b); }
  void set(T v, [[maybe_unused]] int k) {
    val = std::min(val, v);
    ls = std::min(ls, v);
  }
  void pull(NodeMin &ll, NodeMin &rr) {
    if (ls != ID2)
      return;
    val = std::min(ll.val, rr.val);
  }
  void push(NodeMin &ll, NodeMin &rr, int k) {
    if (ls == ID2) {
      return;
    } else {
      ll.set(ls, k / 2);
      rr.set(ls, k / 2);
    }
    ls = ID2;
  }
};
using Vec = std::array<int64_t, 2>;
using Mat = std::array<Vec, 2>;
const Mat I = {Vec{1, 0}, {0, 1}};
Vec operator+(Vec a, Vec b) { return Vec{a[0] + b[0], a[1] + b[1]}; }
Mat operator*(Mat a, Mat b) {
  Mat ans{};
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        ans[i][j] += a[i][k] * b[k][j];
  }
  return ans;
}
Vec operator*(Mat a, Vec b) {
  Vec ans{};
  for (int i = 0; i < 2; ++i)
    for (int k = 0; k < 2; ++k)
      ans[i] += a[i][k] * b[k];
  return ans;
}
template <class T> struct Node2 {
  using ValueType = T;
  using RT = T;
  static constexpr RT ID = 0;
  // T val = 0;
  Vec val{};
  Mat l = I;
  Node2() {}
  Node2(T v) : val{v, 0} {}
  operator RT() { return val[1]; }
  static RT comb(RT a, RT b) { return a + b; }
  void updM(Mat m, int k) {
    val = m * val;
    l = m * l;
  }
  void upd(int k) { updM(Mat{Vec{1, 0}, {1, 1}}, k); }
  void set(T v, int k) {
    // k is here for debugging purposes
    assert(k == 1);
    val[0] = v;
  }
  void pull(Node2 &ll, Node2 &rr) {
    if (l != I)
      return;
    val = ll.val + rr.val;
  }
  void push(Node2 &ll, Node2 &rr, int k) {
    if (l == I) {
      return;
    } else {
      ll.updM(l, k / 2);
      rr.updM(l, k / 2);
    }
    l = I;
  }
};

int main() {
#ifdef LOCAL
  cin.open("input.txt");
  cout.rdbuf()->pubsetbuf(0, 0);
  cout.open("output.txt");
#else
  cin.tie(nullptr)->sync_with_stdio(false);
#endif

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

  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
  }
  int rt = a[0];
  std::vector<std::vector<int>> adj(n);
  for (int i = 1; i < n; ++i) {
    int f;
    cin >> f;
    --f;
    adj[a[f]].push_back(a[i]);
  }

  LSeg<NodeMax<int>> ll(n);
  LSeg<NodeMin<int>> rr(n);
  for (int i = 0; i < n; ++i) {
    ll.val[i + ll.sz] = NodeMax<int>(i);
    rr.val[i + rr.sz] = NodeMin<int>(n - 1);
  }
  ll.build(0, n - 1);
  rr.build(0, n - 1);

  std::vector<std::vector<int>> add(n), rem(n);
  auto dfs = [&](auto &self, int node) -> std::set<int> * {
    if ((int)adj[node].size() == 0)
      return new std::set<int>{node};
    std::set<int> *mx = nullptr;
    std::vector<std::set<int> *> rest;
    for (int i : adj[node]) {
      std::set<int> *p = self(self, i);
      if (!mx || (int)p->size() > (int)mx->size()) {
        if (mx)
          rest.push_back(mx);
        mx = p;
      } else {
        rest.push_back(p);
      }
    }

    for (auto &s : rest) {
      for (int u : *s) {
        auto it = mx->upper_bound(u);
        if (it != mx->end()) {
          int v = *std::next(it);
          if (node < u) {
            // rectangle: (node, u], [v, n]
            rr.set(node + 1, u, v - 1);
          } else if (v < node) {
            // rectangle: [1, u], [v, node)
            add[v].push_back(u);
            rem[node].push_back(u);
          }
        }
        if (it != mx->begin()) {
          int v = *std::prev(it);
          if (node < v) {
            // rectangle: (node, v], [u, n]
            rr.set(node + 1, v, u - 1);
          } else if (u < node) {
            // rectangle: [1, v], [u, node)
            add[u].push_back(v);
            rem[node].push_back(v);
          }
        }
      }
      mx->merge(*s);
    }

    return mx;
  };
  dfs(dfs, rt);
  ll.push(0, n - 1);
  rr.push(0, n - 1);
  std::vector<std::vector<int>> mx(n + 1), mi(n);
  for (int i = 0; i < n; ++i) {
    // ans += std::max(0, (int)rr.val[i + rr.sz] - (int)ll.val[i + ll.sz] + 1);
    if ((int)rr.val[i + rr.sz] < i)
      continue;
    mx[(int)rr.val[i + rr.sz] + 1].push_back(i);
    mi[i].push_back(i);
  }
  std::vector<int64_t> ans(m);
  std::vector<std::vector<std::pair<int, int>>> q(n);
  for (int i = 0; i < m; ++i) {
    int l, r;
    cin >> l >> r;
    l--, r--;
    q[r].emplace_back(l, i);
  }

  LSeg<Node2<int64_t>> seg(n);
  std::multiset<int> miX;
  miX.insert(0);
  for (int i = 0; i < n; ++i) {
    for (int j : mx[i])
      seg.set(j, j, 0);
    for (int j : mi[i])
      seg.set(j, j, 1);
    for (int j : rem[i])
      miX.erase(miX.find(j));
    for (int j : add[i])
      miX.insert(j);
    seg.upd(*miX.rbegin(), n - 1);
    for (auto [l, ind] : q[i])
      ans[ind] = seg.query(l, i);
  }
  for (auto &v : ans)
    cout << v << '\n';
}
源文件, 语言: C++20

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3676kb

input:

100 100
5 29 12 16 25 36 18 37 27 47 34 40 20 3 1 42 26 19 33 41 6 22 8 58 32 62 24 15 35 17 59 30 50 61 43 49 39 67 44 21 13 31 68 69 65 64 10 28 38 54 70 63 9 46 66 52 23 7 48 60 55 56 51 2 57 11 53 14 45 4 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
...

output:

0
0
0
0
0
0
0
0
179
0
0
0
0
0
0
0
0
48
0
0
15
0
0
0
0
0
4
3
0
0
0
0
0
0
0
38
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
286
0
0
0
0
1
0
0
0
0
0
0
119
0
5
0
0
0
0
0
0
0
0
5
0
0
78
57
0
7
0
9
0
0
0
0
0
39
0
0
0
0
0
0
0
0
6
0
0

result:

wrong answer 1st numbers differ - expected: '9', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 150ms
memory: 72952kb

input:

200000 1
73119 155820 110077 139724 136809 18709 57745 43535 89117 43647 20295 60551 108184 188031 180437 52363 72969 130559 179796 75852 53879 96998 63387 76458 193661 142318 28260 40465 80050 188507 143795 141018 94880 71333 7644 109237 105208 109509 9779 159914 135096 47638 175577 182927 173100 1...

output:

1519677

result:

wrong answer 1st numbers differ - expected: '216932', found: '1519677'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

服务器时间: 2024-12-03 01:54:32 | 开源项目