QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#543705#8338. Quad Kingdoms ChessShiinaMahiruWA 28ms7752kbC++202.8kb2024-09-01 18:33:192024-09-01 18:33:19

Judging History

你现在查看的是最新测评结果

  • [2024-09-01 18:33:19]
  • 评测
  • 测评结果:WA
  • 用时:28ms
  • 内存:7752kb
  • [2024-09-01 18:33:19]
  • 提交

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'