QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232991#7439. 铃原露露nhuang6850 865ms106252kbC++2010.1kb2023-10-31 08:51:202023-10-31 08:51:20

Judging History

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

  • [2023-10-31 08:51:20]
  • 评测
  • 测评结果：0
  • 用时：865ms
  • 内存：106252kb
查看
  • [2023-10-31 08:51:20]
  • 提交

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<NodeMin<int>> rr(n);
  for (int i = 0; i < n; ++i)
    rr.val[i + rr.sz] = NodeMin<int>(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() && std::next(it) != mx->end()) {
          int v = *std::next(it);
          if (node < u) {
            // rectangle: (node, u], [v, n]
            dbg(node + 1, u, v, n - 1);
            rr.set(node + 1, u, v - 1);
          } else if (v < node) {
            // rectangle: [1, u], [v, node)
            dbg(0, u, v, node - 1);
            add[v].push_back(u + 1);
            rem[node].push_back(u + 1);
          }
        }
        if (it != mx->begin()) {
          int v = *std::prev(it);
          if (node < v) {
            // rectangle: (node, v], [u, n]
            dbg(node + 1, v, u, n - 1);
            rr.set(node + 1, v, u - 1);
          } else if (u < node) {
            // rectangle: [1, v], [u, node)
            dbg(0, v, u, node - 1);
            add[u].push_back(v + 1);
            rem[node].push_back(v + 1);
          }
        }
      }
      mx->merge(*s);
    }

    mx->insert(node);
    return mx;
  };
  dfs(dfs, rt);
  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);
    assert((int)rr.val[i + rr.sz] >= i);
    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);
    if (*miX.rbegin() < n)
      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: 0ms
memory: 3464kb

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:

13
119
52
6
19
19
68
26
205
44
66
41
91
58
33
37
60
145
47
49
52
53
118
36
10
88
50
94
1
59
144
7
59
55
6
72
10
21
118
21
84
53
107
9
65
102
115
22
5
71
101
354
110
32
8
76
38
5
114
13
27
51
11
239
106
94
105
91
69
23
2
21
7
65
113
62
17
116
84
82
140
111
126
12
1
62
129
11
28
75
119
75
45
24
36
114...

result:

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

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 865ms
memory: 106252kb

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:

321330

result:

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

Subtask #4:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

伺服器時間: 2024-12-03 07:22:46 | 開源專案