QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#543705 | #8338. Quad Kingdoms Chess | ShiinaMahiru | WA | 28ms | 7752kb | C++20 | 2.8kb | 2024-09-01 18:33:19 | 2024-09-01 18:33:19 |
Judging History
answer
// #pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
#define lowbits(x) ((x)&((-x)))
#define INF 0x3f3f3f3f
#define uu __int128
#define PI acos(-1)
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<int, pair<int, int> > PII;
constexpr int N=1e5+10, M=2*N;
constexpr int mod=998244353;
constexpr double eps=1e-9;
int nx[] = {0, 0, 1, -1}, ny[] = {1, -1, 0, 0};
int n,m;
int a[N];
ll p[N];
constexpr int base = 182041;
ll inv_base;
ll qmi(ll a, ll b){
ll res = 1;
while(b){
if(b & 1)res = res * a % mod;
a = a * a % mod;
b >>= 1ll;
}
return res;
}
struct seg_tree
{
struct node
{
int l,r;
ll ha;
int mx;
}tr[N << 2];
void build(int k, int l, int r){
tr[k] = {l, r, 0, 0};
if(l == r)return;
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid+1, r);
}
ll cal(int x, int len){
return x * (p[len] - 1 + mod) % mod * inv_base % mod;
}
ll query(int k, int d){
if(d >= tr[k].mx){
return cal(d, tr[k].r - tr[k].l + 1);
}
if(tr[k].l == tr[k].r)return tr[k].mx;
int mid = tr[k].l + tr[k].r >> 1;
if(d >= tr[rs].mx){
return (query(ls, d) * p[tr[k].r - mid] % mod + cal(d, tr[k].r - mid)) % mod;
}
return (tr[k].ha * p[tr[k].r - mid] % mod + query(rs, d)) % mod;
}
void update(int k, int x, int d){
if(tr[k].l == tr[k].r){
tr[k].mx = d;
tr[k].ha = 0;
return;
}
int mid = tr[k].l + tr[k].r >> 1;
if(mid >= x)update(ls, x, d);
else update(rs, x, d);
tr[k].mx = max(tr[ls].mx, tr[rs].mx);
tr[k].ha = query(ls, tr[rs].mx);
}
}st1, st2;
void solve(){
p[0] = 1;
inv_base = qmi(base-1, mod-2);
for(int i=1; i<N; ++i)p[i] = p[i-1] * base % mod;
cin >> n;
st1.build(1, 1, n);
for(int i=1; i<=n; ++i)cin >> a[i], st1.update(1, i, a[i]);
cin >> n;
st2.build(1, 1, n);
for(int i=1; i<=n; ++i)cin >> a[i], st2.update(1, i, a[i]);
cin >> m;
while(m--){
int op,x,v;
cin >> op >> x >> v;
if(op == 1)st1.update(1, x, v);
else st2.update(1, x, v);
// cout << st1.query(1, 0) << ' ' << st2
if(st1.query(1, -1) == st2.query(1, -1))cout << "YES" << endl;
else cout << "NO" << endl;
}
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
int t = 1;
// cout << fixed << setprecision(9)
// cin >> t;
while(t--)solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6420kb
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: 7752kb
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 NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO 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:
wrong answer 5th words differ - expected: 'YES', found: 'NO'