QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409787 | #8338. Quad Kingdoms Chess | bigJ | WA | 41ms | 4256kb | C++23 | 4.0kb | 2024-05-12 18:32:50 | 2024-05-12 18:32:51 |
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 = findPrime(rnd() % 900000000 + 100000000);
const int B = 10;
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);
}
#undef m
};
struct Info {
int l;
int r;
int max;
int premin;
int hash;
int siz;
Info() : l(-1), r(-1), max(0), premin(N + 1), hash(0), siz(1) {}
Info(int v) : l(0), r(0), max(v), premin(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;
}
Info c = a;
c.r = b.r;
if (c.max > b.max) {
return c;
}
Info d = b;
if (d.premin < c.max) {
int pos = *std::ranges::partition_point(std::views::iota(b.l, b.r), [&](int m) {
return seg.rangeQuery(m, b.r).premin < c.max;
});
d = seg.rangeQuery(pos, b.r);
}
c.max = d.max;
c.siz += d.siz;
c.hash = (c.hash + 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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3952kb
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: 4256kb
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: 34ms
memory: 4096kb
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: 37ms
memory: 4004kb
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: 30ms
memory: 4236kb
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: 28ms
memory: 3972kb
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: -100
Wrong Answer
time: 41ms
memory: 4240kb
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 NO YES YES NO NO NO NO NO NO NO NO NO NO N...
result:
wrong answer 87th words differ - expected: 'YES', found: 'NO'