QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#375498 | #8338. Quad Kingdoms Chess | isaunoya | WA | 40ms | 3832kb | C++23 | 3.5kb | 2024-04-03 11:31:16 | 2024-04-03 11:31:17 |
Judging History
answer
#if defined(LOCAL)
#include <D:/cp/templates/my_template_compiled.hpp>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt")
#include <bits/stdc++.h>
#define debug(...) 42
#define rep1(a) for (auto i = 0; i < a; i++)
#define rep2(i, a) for (auto i = 0; i < a; i++)
#define rep3(i, a, b) for (auto i = a; i < b; i++)
#define rep4(i, a, b, c) for (auto i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define pb emplace_back
using namespace std;
template <typename T, typename T2> void cmin(T &x, const T2 &y) {
x = x < y ? x : y;
}
template <typename T, typename T2> void cmax(T &x, const T2 &y) {
x = x > y ? x : y;
}
template <typename T> using vc = vector<T>;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937 rng(2813289);
const int INF = 1000000000;
const ll LNF = 1000000000000000000;
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define fi first
#define se second
#endif
// using ull = unsigned long long;
const int mod = 1e9 + 7;
map<int, ll> foo;
vi get_stk(vi a) {
vi stk;
for (auto ai : a) {
while (!stk.empty() && stk.back() < ai) {
stk.pop_back();
}
stk.pb(ai);
}
return stk;
}
struct array {
int n;
vi a;
array() {}
array(int N) { n = N; }
void init(int N) {
n = N;
a.resize(n);
rep(i, n) cin >> a[i];
rep(i, n) {
if (!foo.count(a[i])) {
foo[a[i]] = rng();
}
}
leaf.resize(n * 4);
mx.resize(n * 4);
tr.resize(n * 4);
build(0, n, 1);
}
vi leaf, mx;
vc<ll> tr;
ll calc(int p, int x) {
if (x > mx[p]) {
return 1;
} else if (leaf[p]) {
if (x <= mx[p]) {
return foo[mx[p]];
} else {
return 1;
}
}
if (x > mx[p * 2 + 1]) { // x <= mx[p * 2]
return calc(p * 2, x);
} else { // x <= mx[p * 2 + 1]
return tr[p] * calc(p * 2 + 1, x) % mod;
}
}
void pull(int p) {
mx[p] = max(mx[p * 2], mx[p * 2 + 1]);
tr[p] = calc(p * 2, mx[p * 2 + 1]);
}
void build(int l, int r, int p) {
if (r - l == 1) {
leaf[p] = 1;
mx[p] = a[l];
return;
}
int m = (l + r) / 2;
build(l, m, p * 2);
build(m, r, p * 2 + 1);
pull(p);
}
void modify(int l, int r, int p, int x, int v) {
if (r - l == 1) {
leaf[p] = 1;
mx[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(l, m, p * 2, x, v);
} else {
modify(m, r, p * 2 + 1, x, v);
}
pull(p);
}
void modify(int x, int y) {
a[x] = y;
modify(0, n, 1, x, y);
}
ll sol() { return calc(1, -1); }
// void modify(int x, int y) { a[x] = y; }
// vi stk() { return get_stk(a); }
} a[2];
void solve() {
int n[2];
cin >> n[0];
a[0].init(n[0]);
cin >> n[1];
a[1].init(n[1]);
int Q;
cin >> Q;
while (Q--) {
int p, x, y;
cin >> p >> x >> y;
--p;
--x;
if (!foo.count(y)) {
foo[y] = rng();
}
a[p].modify(x, y);
// cout << (a[0].stk() == a[1].stk() ? "YES" : "NO") << "\n";
cout << (a[0].sol() == a[1].sol() ? "YES" : "NO") << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
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: 35ms
memory: 3832kb
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: 3604kb
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: -100
Wrong Answer
time: 40ms
memory: 3648kb
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:
wrong answer 180th words differ - expected: 'YES', found: 'NO'