QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694379#8338. Quad Kingdoms Chesssnow_mikumikuWA 1ms8528kbC++143.1kb2024-10-31 17:49:282024-10-31 17:49:30

Judging History

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

  • [2024-10-31 17:49:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8528kb
  • [2024-10-31 17:49:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using UL = unsigned long long;
const UL mi = 995329;
const int N = 1e5 + 10;

UL m995[N], a[N], b[N];
struct tree {
    UL max, hs;
}A[N << 2], B[N << 2];

UL ask(int p, UL mx, int ty, int l, int r) 
{
    int mid = l + r >> 1;
    if(!ty) {
        if(A[p].max < mx) return 0;
        if(l == r) return A[p].hs;
        if(A[p * 2].max < mx) 
            return ask(p * 2 + 1, mx, ty, mid + 1, r);
        else 
            return A[p].hs - A[p * 2].hs + ask(p * 2, mx, ty, l, mid);
    }

    else {
        if(B[p].max < mx) return 0;
        if(l == r) return B[p].hs;
        if(B[p * 2].max < mx) 
            return ask(p * 2 + 1, mx, ty, mid + 1, r);
        else 
            return B[p].hs - B[p * 2].hs + ask(p * 2, mx, ty, l, mid);
    }
}

void build(int p, int l, int r, int ty)
{
    if(!ty) {
        if(l == r) {
            A[p].hs = m995[a[l]];
            A[p].max = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(p * 2, l, mid, 0);
        build(p * 2 + 1, mid + 1, r, 0);

        A[p].max = max(A[p * 2].max, A[p * 2 + 1].max);
        A[p].hs = A[p * 2].hs + ask(p * 2 + 1, A[p * 2].max, 1, mid + 1, r);
    }

    else {
        if(l == r) {
            B[p].hs = m995[b[l]];
            B[p].max = b[l];
            return;
        }
        int mid = l + r >> 1;
        build(p * 2, l, mid, 1);
        build(p * 2 + 1, mid + 1, r, 1);

        B[p].max = max(B[p * 2].max, B[p * 2 + 1].max);
        B[p].hs = B[p * 2].hs + ask(p * 2 + 1, B[p * 2].max, 1, mid + 1, r);
    }
}

void change(int x, int p, UL To, int ty, int l, int r)
{
    if(!ty) {
        if(l == r) {
            A[p].hs = m995[To] * To;
            A[p].max = To;
            return;
        }
        int mid = l + r >> 1;
        if(x <= mid) change(x, p * 2, To, ty, l, mid);
        else change(x, p * 2 + 1, To, ty, mid + 1, r);

        A[p].max = max(A[p * 2].max, A[p * 2 + 1].max);
        A[p].hs = A[p * 2].hs + ask(p * 2 + 1, A[p * 2].max, 1, mid + 1, r);
    }

    else {
        if(l == r) {
            B[p].hs = m995[To] * To;
            B[p].max = To;
            return;
        }
        int mid = l + r >> 1;
        if(x <= mid) change(x, p * 2, To, ty, l, mid);
        else change(x, p * 2 + 1, To, ty, mid + 1, r);

        B[p].max = max(B[p * 2].max, B[p * 2 + 1].max);
        B[p].hs = B[p * 2].hs + ask(p * 2 + 1, B[p * 2].max, 1, mid + 1, r);
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    m995[0] = 1;
    for(int i = 1; i < N; i++) m995[i] = m995[i - 1] * mi;

    int n, m, q;
    cin >> n;
    for(int i = n; i >= 1; i--) cin >> a[i];
    cin >> m;
    for(int i = m; i >= 1; i--) cin >> b[i];
    build(1, 1, n, 0);
    build(1, 1, m, 1);

    int op, x, y;
    cin >> q;
    for(int i = 1; i <= q; i++) {
        cin >> op >> x >> y;
        if(op == 1) x = n - x + 1, change(x, 1, y, 0, 1, n);
        if(op == 2) x = m - x + 1, change(x, 1, y, 1, 1, m);
        if(B[1].hs == A[1].hs) cout << "YES\n";
        else cout << "NO\n"; 
    }
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 8528kb

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
NO

result:

wrong answer 8th words differ - expected: 'YES', found: 'NO'