QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#409896 | #8338. Quad Kingdoms Chess | bigJ | TL | 48ms | 4392kb | C++23 | 4.3kb | 2024-05-12 21:21:24 | 2024-05-12 21:21:24 |
Judging History
answer
#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: 4352kb
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: 33ms
memory: 4224kb
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: 38ms
memory: 4392kb
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: 45ms
memory: 4096kb
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: 4108kb
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: 33ms
memory: 4352kb
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: 45ms
memory: 4224kb
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: 34ms
memory: 4224kb
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: 44ms
memory: 4228kb
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: 4232kb
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: 36ms
memory: 4164kb
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: 4176kb
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 ...