QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #469719 | #8338. Quad Kingdoms Chess | real_sigma_team | WA | 28ms | 12260kb | C++23 | 3.1kb | 2024-07-09 22:23:31 | 2024-07-09 22:23:32 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")
#ifdef lisie_bimbi
#define debug(x) cout << #x << " : " << x << endl;
#else
#define endl '\n'
#endif
//#define int long long
#define inf 1000000000000000000
#define double long double
typedef long long ll;
ll so[100005];
struct segtree{
int v[100000];
int mx[400000];
ll hs[400000];
ll get(int u, int l, int r, int x){
if(l + 1 == r){
if(mx[u] >= x){
return hs[u];
}else{
return 0;
}
}
int m = (l + r) / 2;
if(mx[u * 2 + 1] < x){
return get(u * 2 + 2, m, r, x);
}else{
return get(u * 2 + 1, l, m, x) ^ (hs[u] ^ hs[u * 2 + 1]);
}
}
void build(int u, int l, int r){
if(l + 1 == r){
mx[u] = v[l];
hs[u] = so[v[l]];
}else{
int m = (l + r) / 2;
build(u * 2 + 1, l, m);
build(u * 2 + 2, m, r);
mx[u] = max(mx[u * 2 + 1], mx[u * 2 + 2]);
hs[u] = hs[u * 2 + 1] ^ get(u * 2 + 2, m, r, mx[u * 2 + 1]);
}
}
void update(int u, int l, int r, int ind, int new_val){
if(l + 1 == r){
v[l] = new_val;
mx[u] = v[l];
hs[u] = so[v[l]];
}else{
int m = (l + r) / 2;
if(ind < m){
update(u * 2 + 1, l, m, ind, new_val);
}else{
update(u * 2 + 2, m, r, ind, new_val);
}
mx[u] = max(mx[u * 2 + 1], mx[u * 2 + 2]);
hs[u] = hs[u * 2 + 1] ^ get(u * 2 + 2, m, r, mx[u * 2 + 1]);
}
}
};
mt19937_64 rnd(239);
segtree st1, st2;
signed main() {
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif
for(int i = 0; i < 100005; i++){
so[i] = rnd();
}
int n1;
cin >> n1;
for(int i = 0; i < n1; i++){
cin >> st1.v[n1 - 1 - i];
}
st1.build(0, 0, n1);
int n2;
cin >> n2;
for(int i = 0; i < n2; i++){
cin >> st2.v[n2 - 1 - i];
}
st2.build(0, 0, n2);
int m;
cin >> m;
while(m--){
int t, x, y;
cin >> t >> x >> y;
x--;
if(t == 1){
x = n1 - 1 - x;
st1.update(0, 0, n1, x, y);
if(st1.get(0, 0, n1, 0) == st2.get(0, 0, n2, 0)){
cout << "YES\n";
}else{
cout << "NO\n";
}
}else{
x = n2 - 1 - x;
st2.update(0, 0, n2, x, y);
if(st1.get(0, 0, n1, 0) == st2.get(0, 0, n2, 0)){
cout << "YES\n";
}else{
cout << "NO\n";
}
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 8616kb
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: -100
Wrong Answer
time: 28ms
memory: 12260kb
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 YES YES YES YES NO YES YES YES NO NO NO YES NO NO YES YES YES NO NO YES YES NO YES YES YES NO YES NO NO YES NO NO NO NO NO NO NO YES NO YES NO NO NO YE...
result:
wrong answer 48th words differ - expected: 'NO', found: 'YES'