QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409897 | #8338. Quad Kingdoms Chess | bigJ | TL | 48ms | 4260kb | C++20 | 4.4kb | 2024-05-12 21:22:26 | 2024-05-12 21:22:27 |
Judging History
answer
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
constexpr bool isprime(int n) {
if (n <= 1) {
return false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
constexpr int findPrime(int n) {
while (!isprime(n)) {
n++;
}
return n;
}
std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
const int P = 998244353;
const int B = rnd() % P;
constexpr int N = 100000;
int p[N + 1];
template <class Info>
struct SegmentTree {
#define m (l + r) / 2
int n;
std::vector<Info> tr;
SegmentTree() : n(0) {}
SegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
SegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
tr.assign(4 << std::__lg(n), Info());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
tr[p] = init_[l];
tr[p].l = l;
tr[p].r = r;
return;
}
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
tr[p] = merge(tr[2 * p], tr[2 * p + 1], *this);
}
void modify(int p, int l, int r, int x, const Info& v) {
if (r - l == 1) {
tr[p] = v;
tr[p].l = l;
tr[p].r = r;
return;
}
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int x, const Info& v) {
modify(1, 0, n, x, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return tr[p];
}
return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y), *this);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
int find(int p, int l, int r, int x, int y, int v) {
if (l >= y || r <= x || tr[p].max < v) {
return -1;
}
if (r - l == 1) {
return l;
}
int res = find(2 * p, l, m, x, y, v);
if (res == -1) {
res = find(2 * p + 1, m, r, x, y, v);
}
return res;
}
int find(int x, int y, int v) {
return find(1, 0, n, x, y, v);
}
#undef m
};
struct Info {
int l;
int r;
int max;
int hash;
int siz;
Info(int v = 0) : l(-1), r(-1), max(v), hash(1LL * v * B % P), siz(1) {}
};
Info merge(const Info& a, const Info& b, SegmentTree<Info>& seg) {
if (a.l == -1) {
return b;
} else if (b.l == -1) {
return a;
}
if (a.max > b.max) {
Info c = a;
c.r = a.r;
return c;
}
int pos = seg.find(b.l, b.r, a.max);
if (pos == -1) {
pos = b.l;
}
Info d = seg.rangeQuery(pos, b.r);
Info c{};
c.l = a.l;
c.r = b.r;
c.max = std::max(a.max, b.max);
c.siz = a.siz + d.siz;
c.hash = (a.hash + 1LL * d.hash * p[a.siz] % P) % P;
return c;
}
int main() {
p[0] = 1;
for (int i = 1; i <= N; i++) {
p[i] = (1LL * p[i - 1] * B) % P;
}
int n1, n2, m;
scanf("%d", &n1);
std::vector<int> a(n1);
for (int i = 0; i < n1; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &n2);
std::vector<int> b(n2);
for (int i = 0; i < n2; i++) {
scanf("%d", &b[i]);
}
std::ranges::reverse(a);
std::ranges::reverse(b);
SegmentTree<Info> sega(a);
SegmentTree<Info> segb(b);
for (scanf("%d", &m); m; m--) {
int o, x, y;
scanf("%d%d%d", &o, &x, &y);
if (o == 1) {
sega.modify(n1 - x, y);
} else {
segb.modify(n2 - x, y);
}
puts(sega.tr[1].hash == segb.tr[1].hash ? "YES" : "NO");
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 4216kb
input:
5 1 2 3 4 5 5 5 4 3 2 1 8 1 1 5 1 4 2 1 2 4 1 5 1 1 5 5 2 1 4 2 3 5 2 5 5
output:
NO NO NO YES NO NO NO YES
result:
ok 8 tokens
Test #2:
score: 0
Accepted
time: 37ms
memory: 3972kb
input:
1 2 6 2 1 1 1 1 1 200000 2 6 2 1 1 1 1 1 1 1 1 2 2 1 1 1 1 2 1 1 1 2 4 1 2 1 2 1 1 1 1 1 2 2 5 1 1 1 1 1 1 2 1 1 1 2 6 1 1 1 2 1 1 2 1 1 2 2 3 1 1 1 1 2 1 1 2 6 2 1 1 2 2 4 1 1 1 2 2 6 1 1 1 2 1 1 1 2 5 2 2 6 2 1 1 1 2 4 2 2 5 2 2 6 2 1 1 1 2 5 1 2 6 2 1 1 2 1 1 1 1 1 1 2 4 1 1 1 2 1 1 2 1 1 2 2 3 2...
output:
NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #3:
score: 0
Accepted
time: 32ms
memory: 4052kb
input:
6 2 1 1 2 1 2 1 1 200000 2 1 1 1 1 2 1 1 1 2 1 2 2 1 1 2 1 1 2 1 2 2 1 2 1 1 2 1 3 1 1 6 2 1 5 2 1 4 2 1 3 1 2 1 2 1 4 2 1 4 2 2 1 2 2 1 2 1 3 1 1 6 1 1 1 2 2 1 1 1 6 1 1 3 1 1 5 2 1 6 2 1 5 2 2 1 2 1 2 1 1 5 2 2 1 1 2 1 1 1 6 1 2 1 2 2 1 1 1 3 2 2 1 1 1 6 1 1 4 2 1 2 1 1 1 1 2 1 1 1 2 1 1 6 2 1 6 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #4:
score: 0
Accepted
time: 47ms
memory: 4052kb
input:
6 1 3 1 2 1 2 6 2 1 3 3 3 1 200000 2 4 2 1 2 1 1 6 2 2 3 2 1 1 1 1 6 2 1 6 2 1 3 2 2 6 1 2 4 3 1 1 2 2 5 2 2 6 2 2 3 1 1 4 3 1 3 1 2 5 2 2 4 2 2 1 3 1 1 1 2 2 2 2 4 2 1 5 3 1 6 3 2 6 3 1 5 3 2 5 3 2 4 1 2 4 2 1 1 2 1 6 1 2 6 1 1 2 3 1 1 3 1 1 1 2 6 3 2 4 1 1 4 2 2 2 1 1 3 1 1 1 3 1 1 3 1 4 3 1 3 3 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #5:
score: 0
Accepted
time: 31ms
memory: 4160kb
input:
4 1 1 2 2 1 1 200000 2 1 2 1 1 3 1 2 1 2 1 2 2 1 2 2 1 3 2 1 1 2 1 1 1 4 2 2 1 3 1 3 1 1 2 1 1 3 2 2 1 1 1 4 2 2 1 1 2 1 2 1 1 1 2 1 2 2 1 1 1 4 1 1 2 2 2 1 1 1 1 1 1 4 3 2 1 3 1 1 3 2 1 2 1 2 1 2 1 1 2 1 1 2 1 1 2 1 3 2 1 2 1 2 3 2 1 3 1 3 3 2 1 1 1 2 3 2 1 2 1 1 2 2 1 2 2 1 3 1 2 1 1 4 3 2 1 2 2 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO YES NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #6:
score: 0
Accepted
time: 29ms
memory: 4112kb
input:
2 4 2 4 2 3 3 2 200000 1 1 2 1 2 2 1 2 2 1 2 4 1 1 2 1 2 4 2 2 1 1 1 3 2 3 2 2 3 1 2 2 4 2 3 2 2 2 1 1 1 4 1 2 4 2 2 1 1 1 2 2 1 2 2 4 4 1 2 4 1 2 3 2 4 4 2 3 1 2 1 3 2 3 1 2 2 1 1 1 2 2 2 1 1 2 3 1 2 2 1 2 1 1 2 4 1 2 4 1 1 3 1 1 4 2 1 3 1 1 1 1 2 4 2 1 2 2 3 4 1 2 4 2 2 1 1 2 1 2 3 2 1 2 3 2 3 3 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 200000 tokens
Test #7:
score: 0
Accepted
time: 47ms
memory: 4036kb
input:
7 3 3 4 1 1 3 3 5 3 3 2 1 4 200000 2 2 1 2 2 1 2 5 1 1 6 1 1 5 2 2 1 4 1 4 2 1 6 4 1 7 1 1 2 3 2 5 1 2 5 4 1 6 2 1 5 2 1 4 1 1 2 1 2 2 2 1 3 4 1 7 2 1 6 3 2 5 1 1 5 1 1 7 3 2 1 3 2 3 1 1 3 2 2 2 2 1 7 4 2 1 4 1 3 2 1 1 2 1 5 3 1 5 3 2 2 2 1 5 3 2 5 3 2 3 2 1 1 3 1 2 2 2 2 1 2 1 4 2 1 2 1 3 4 2 1 1 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #8:
score: 0
Accepted
time: 37ms
memory: 4052kb
input:
1 3 7 4 4 5 5 5 5 4 200000 2 2 4 2 6 4 1 1 4 2 6 4 2 1 3 2 2 3 2 1 3 1 1 5 1 1 5 2 3 5 1 1 4 1 1 4 2 6 5 2 5 1 2 1 2 2 7 2 1 1 5 2 4 5 1 1 2 1 1 3 2 4 2 2 1 3 1 1 3 2 1 1 1 1 1 2 3 1 1 1 4 1 1 5 1 1 1 2 5 2 2 7 3 1 1 5 2 6 4 1 1 4 2 7 4 2 3 3 2 3 1 1 1 3 1 1 3 2 4 4 1 1 4 1 1 2 1 1 1 2 3 1 2 1 1 1 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #9:
score: 0
Accepted
time: 42ms
memory: 4004kb
input:
8 3 1 2 2 1 4 4 4 3 1 4 4 200000 1 2 1 1 5 1 2 1 1 2 1 1 2 2 2 2 3 1 1 5 5 1 6 2 1 2 5 1 3 1 1 5 1 2 1 5 2 1 2 1 4 4 2 3 3 1 4 3 2 2 2 2 3 1 1 6 4 1 1 3 1 2 3 2 2 5 2 3 3 2 1 3 2 3 4 2 1 4 2 2 5 2 2 4 2 2 2 1 3 1 1 8 2 2 2 3 1 2 2 1 1 2 1 1 1 1 3 1 2 1 3 2 2 3 1 6 2 2 2 4 1 6 3 2 1 1 1 1 4 2 1 4 2 1...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #10:
score: 0
Accepted
time: 32ms
memory: 4156kb
input:
3 6 1 5 2 5 3 200000 1 2 4 1 1 3 1 2 5 2 2 5 1 3 3 1 1 6 1 3 1 1 2 1 2 1 6 2 1 4 2 1 2 2 2 3 1 3 1 1 3 5 1 2 4 2 2 5 1 2 5 1 3 1 2 1 3 1 2 6 1 2 4 2 1 3 1 2 4 1 2 1 1 3 2 2 2 6 2 1 4 2 2 4 1 1 2 1 1 4 2 2 2 2 1 4 1 2 2 1 1 3 2 1 4 1 3 3 2 1 6 2 2 2 1 1 6 1 3 6 1 2 2 1 3 1 2 2 3 1 2 2 2 1 2 2 2 5 2 2...
output:
NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #11:
score: 0
Accepted
time: 35ms
memory: 4260kb
input:
3 1 1 6 5 2 3 4 4 6 200000 2 3 5 2 5 5 1 1 4 1 2 4 1 1 1 2 4 3 2 1 2 1 1 6 2 2 2 2 5 4 1 3 4 1 3 4 2 3 5 2 1 6 1 1 1 2 3 4 2 3 5 2 2 5 1 1 5 1 2 2 1 3 2 2 2 1 1 3 5 2 3 6 1 3 3 2 1 3 2 5 3 1 1 1 2 4 4 2 5 1 2 2 5 1 2 2 1 2 3 2 4 5 1 3 5 2 1 1 2 5 1 1 2 1 2 5 4 2 3 1 2 1 6 1 1 2 1 3 6 1 2 1 2 3 6 1 1...
output:
YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 200000 tokens
Test #12:
score: 0
Accepted
time: 48ms
memory: 4156kb
input:
8 73198 31688 65092 21397 35031 58089 52944 16010 5 31090 97692 26708 44940 89767 200000 2 5 31191 1 1 60759 1 6 70508 1 2 97983 2 3 53563 1 4 22102 1 7 36211 1 3 33339 1 8 49224 1 7 82146 2 5 97668 1 4 13552 1 2 26414 2 4 3381 1 4 42198 1 4 28786 2 2 29892 2 2 77347 1 5 53766 2 5 55142 2 5 74266 1 ...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 200000 tokens
Test #13:
score: -100
Time Limit Exceeded
input:
100000 45952 97807 4941 35929 10776 28013 47912 21386 48030 55110 1347 96260 91732 78252 37717 2556 44017 67045 91588 59689 86623 88384 41158 38652 77627 83554 48557 85544 94827 54704 86949 61451 79790 92480 74798 43911 65450 20096 17129 95952 87522 98877 41827 51143 42419 98384 27210 34607 91233 46...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...