QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#647166#7434. 冷たい部屋、一人guosounRE 0ms0kbC++173.1kb2024-10-17 12:16:452024-10-17 12:16:45

Judging History

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

  • [2024-10-17 12:16:45]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-10-17 12:16:45]
  • 提交

answer

#include <bits/stdc++.h>
using ll = long long;

template <int B>
struct array {
  std::vector<int> a, b;
  array(int n) : a(n), b((n - 1) / B + 1) {}
  void add(int x) { a[x] += 1, b[x / B] += 1; }
  int query(int x) {
    int ret = 0;
    for (int i = x; i / B == x / B && i < (int)a.size(); i++) ret += a[i];
    for (int i = x / B + 1; i < (int)b.size(); i++) ret += b[i];
    return ret;
  }
};

struct list {
  ll ans;
  std::vector<int> f;
  std::vector<std::pair<int*, int>> st1;
  std::vector<ll> st2;
  
  list(int n) : ans(0), f(n) { std::iota(f.begin(), f.end(), 0); }
  std::tuple<int, int, int, int> link(int i) {
    int s = f[i], t = f[i + 1];
    st2.emplace_back(ans);
    ans += (ll)(i - s + 1) * (t - i + 1);
    st1.emplace_back(&f[s], f[s]), st1.emplace_back(&f[t], f[t]);
    f[s] = t, f[t] = s;
    return {s, i, i + 1, t};
  }
  void undo() {
    *st1.back().first = st1.back().second, st1.pop_back();
    *st1.back().first = st1.back().second, st1.pop_back();
    ans = st2.back(), st2.pop_back();
  }
};

template<class T, class cmp>
struct rmq {
  int n;
  std::vector<T> a;
  std::array<std::vector<T>, 20> bl;
  rmq(std::vector<T> v) {
    n = v.size(), a = v;
    bl.fill(std::vector<T>(n));
    for (int i = 0; i < n; i++) bl[0][i] = a[i];
    for (int i = 1; i < 20; i++) 
      for (int j = 0; j + (1 << i) - 1 < n; j++)
        bl[i][j] = std::min(bl[i - 1][j], bl[i - 1][j + (1 << (i - 1))], cmp());
  }
  T query(int l, int r) {
    int k = std::__lg(r - l + 1);
    return std::min(bl[k][l], bl[k][r - (1 << k) + 1], cmp());
  }
};

int main() {
  const int B = 320;
  std::cin.tie(0)->sync_with_stdio(0);
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n + 1), b(n + 1);
  std::vector<std::vector<int>> pos(n + 1);
  std::vector<std::tuple<int, int, ll*>> q(m);
  std::vector<ll> ans;
  ans.reserve(m);
  for (int i = 1; i <= n; i++) std::cin >> a[i], pos[a[i]].emplace_back(i);
  for (int i = 1; i <= n; i++) std::cin >> b[i];
  for (auto &[l, r, it] : q) {
    std::cin >> l >> r;
    ans.push_back(0);
    it = &ans.back();
  }
  rmq<int, std::less<int>> bmn(b);
  rmq<int, std::greater<int>> bmx(b);
  std::vector<std::pair<int, int>> e;
  for (int i = 1; i < n; i++) e.emplace_back(std::max(b[i], b[i + 1]), i);
  std::sort(e.begin(), e.end());
  std::sort(q.begin(), q.end(), [](auto x, auto y) {
    return std::get<1>(x) < std::get<1>(y);
  });
  auto it = q.begin();
  list l(n + 1);
  array<400> cnt(n + 1);

  for (auto [v, i] : e) {
    // cpp_dump(v);
    while (it != q.end() && std::get<1>(*it) < v)  {
      *std::get<2>(*it) += cnt.query(std::get<0>(*it)), it++;
    }
    auto [l1, r1, l2, r2] = l.link(i);
    if (r1 - l1 > r2 - l2) std::swap(l1, l2), std::swap(r1, r2);
    for (int i = l1; i <= r1; i++) {
      if (pos[a[i]].size() > B) continue;
      for (int j : pos[a[i]])
        if (l2 <= j && j <= r2) cnt.add(bmn.query(i, j));
    }
  }
  while (it != q.end()) {
    *std::get<2>(*it) += cnt.query(std::get<0>(*it)), it++;
  }
  for (int i = 0; i < m; i++) std::cout << ans[i] << '\n';
  
}

详细

Test #1:

score: 0
Runtime Error

input:

100 100
4 1 5 1 2 1 7 5 3 7 2 3 6 6 5 3 2 2 4 1 6 5 6 2 2 2 7 6 1 3 6 3 5 6 7 6 1 2 3 3 4 2 1 1 5 4 4 3 6 7 1 1 6 1 5 6 2 3 7 4 2 4 6 7 7 3 5 3 7 2 3 3 5 1 4 7 1 2 2 5 2 2 4 3 4 7 2 7 7 3 7 3 6 6 5 4 5 4 7 6
93 52 12 70 25 36 18 37 27 99 68 40 84 3 76 57 60 19 33 41 92 87 58 13 15 43 28 63 64 59 31 ...

output:


result: