QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#722480 | #8546. Min or Max 2 | guosoun | Compile Error | / | / | C++17 | 3.0kb | 2024-11-07 19:11:44 | 2024-11-07 19:11:45 |
Judging History
This is the latest submission verdict.
- [2024-11-07 19:11:45]
- Judged
- Verdict: Compile Error
- Time: 0ms
- Memory: 0kb
- [2024-11-07 19:11:44]
- Submitted
answer
#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#include <bits/stdc++.h>
using ll = long long;
struct matrix {
std::array<int, 9> a;
matrix() : a{} {}
matrix operator*(matrix b) {
matrix ret;
for (int i = 0; i < 9; i++) {
if (a[i] >> 0 & 1) ret.a[i] |= b.a[0];
if (a[i] >> 1 & 1) ret.a[i] |= b.a[1];
if (a[i] >> 2 & 1) ret.a[i] |= b.a[2];
if (a[i] >> 3 & 1) ret.a[i] |= b.a[3];
if (a[i] >> 4 & 1) ret.a[i] |= b.a[4];
if (a[i] >> 5 & 1) ret.a[i] |= b.a[5];
if (a[i] >> 6 & 1) ret.a[i] |= b.a[6];
if (a[i] >> 7 & 1) ret.a[i] |= b.a[7];
if (a[i] >> 8 & 1) ret.a[i] |= b.a[8];
if (a[i] >> 9 & 1) ret.a[i] |= b.a[9];
}
return ret;
}
};
template <class T>
struct sgt {
int n;
std::vector<T> tr;
int ls(int i) { return i << 1; }
int rs(int i) { return i << 1 | 1; }
void update(int i, int l, int r, int p, T x) {
if (l == r) return tr[i] = x, void();
int mid = (l + r) >> 1;
if (p <= mid)
update(ls(i), l, mid, p, x);
else
update(rs(i), mid + 1, r, p, x);
tr[i] = tr[ls(i)] * tr[rs(i)];
}
T query() { return tr[1]; }
void update(int p, T v) { update(1, 0, n - 1, p, v); }
sgt() {}
sgt(int n) : n(n), tr(n * 4) {}
};
struct checker {
int n, x, y;
std::vector<int> a, b, pa, pb;
sgt<matrix> tr;
void update(int i) {
int av = a[i] < x ? 0 : a[i] == x ? 1 : 2;
int bv = b[i] < y ? 0 : b[i] == y ? 1 : 2;
matrix ma;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
ma.a[i * 3 + j] |= 1 << (std::min(i, av) * 3 + std::min(j, bv));
ma.a[i * 3 + j] |= 1 << (std::max(i, av) * 3 + std::max(j, bv));
}
tr.update(i, ma);
}
bool query(int qx, int qy) {
while (x > qx) --x, update(pa[x + 1]), update(pa[x]);
while (x < qx) ++x, update(pa[x - 1]), update(pa[x]);
while (y > qy) --y, update(pb[y + 1]), update(pb[y]);
while (y < qy) ++y, update(pb[y - 1]), update(pb[y]);
int av = a[0] < x ? 0 : a[0] == x ? 1 : 2;
int bv = b[0] < y ? 0 : b[0] == y ? 1 : 2;
return tr.query().a[av * 3 + bv] >> (1 * 3 + 1) & 1;
}
checker(std::vector<int> a, std::vector<int> b)
: n(a.size()), x(0), y(0), a(a), b(b), pa(n + 1), pb(n + 1) {
tr = sgt<matrix<9>>(n);
for (int i = 0; i < n; i++) pa[a[i]] = i, pb[b[i]] = i, update(i);
}
};
void mian() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (auto &x : a) std::cin >> x;
for (auto &x : b) std::cin >> x;
checker chk(a, b);
std::vector<int> ans(n);
int i = 1, j = 1;
while (i <= n || j <= n) {
ans[std::abs(i - j)] += 1;
if (i < n && chk.query(i + 1, j)) i += 1;
else if (j < n && chk.query(i, j + 1)) j += 1;
else i += 1, j += 1;
}
for (int i : ans) std::cout << i << ' ';
std::cout << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--) mian();
}
详细
answer.code: In constructor ‘checker::checker(std::vector<int>, std::vector<int>)’: answer.code:74:14: error: ‘matrix’ is not a template 74 | tr = sgt<matrix<9>>(n); | ^~~~~~