QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693004#8338. Quad Kingdoms Chesssnow_mikumikuWA 32ms8540kbC++143.7kb2024-10-31 15:21:442024-10-31 15:21:49

Judging History

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

  • [2024-10-31 15:21:49]
  • 评测
  • 测评结果:WA
  • 用时:32ms
  • 内存:8540kb
  • [2024-10-31 15:21:44]
  • 提交

answer

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

UL m995[N], a[N], b[N];
struct tree {
    int l, r;
    UL cnt;
    UL max, hs, minstk;
    friend tree operator + (tree &a, tree &b) {
        tree ans;
        ans.cnt = a.cnt + b.cnt;
        ans.minstk = a.minstk;
        if(!a.minstk) ans.minstk = b.minstk;
        if(a.max > b.max) ans.max = a.max;
        else ans.max = b.max;
        ans.hs = a.hs * m995[b.cnt] + b.hs;
        return ans;
    }
}A[N << 3], B[N << 3], nul;

tree ask(int p, UL mx, int ty) 
{
    if(!ty) {
        if(!A[p].l || A[p].max < mx) return nul;
        if(A[p].l == A[p].r && A[p].minstk < mx) return nul;
        if(A[p].minstk >= mx) return A[p];

        if(A[p * 2].max < mx) 
            return ask(p * 2 + 1, mx, ty);
        else {
            tree tmp = ask(p * 2, mx, ty);
            return tmp + A[p * 2 + 1];
        }
            
    }

    else {
        if(!B[p].l || B[p].max < mx) return nul;
        if(B[p].l == B[p].r && B[p].minstk < mx) return nul;
        if(B[p].minstk >= mx) return B[p];

        if(B[p * 2].max < mx) 
            return ask(p * 2 + 1, mx, ty);
        else {
            tree tmp = ask(p * 2, mx, ty);
            return tmp + B[p * 2 + 1];
        }
    }
}

void update(tree &w, tree &u) {
    w.cnt = u.cnt;
    w.hs = u.hs;
    w.max = u.max;
    w.minstk = u.minstk;
}

void build(int l, int r, int p, int ty) 
{
    if(!ty) {
        A[p].l = l, A[p].r = r;
        if(l == r) {
            A[p].cnt = 1;
            A[p].max = A[p].hs = A[p].minstk = a[l];
            return;
        }
    }
    else {
        B[p].l = l, B[p].r = r;
        if(l == r) {
            B[p].cnt = 1;
            B[p].max = B[p].hs = B[p].minstk = b[l];
            return;
        }
    }
    int mid = l + r >> 1;
    build(l, mid, p * 2, ty);
    build(mid + 1, r, p * 2 + 1, ty);
    if(!ty) {
        tree tmp = ask(p * 2 + 1, A[p * 2].max, ty);
        tmp = A[p * 2] + tmp;
        update(A[p], tmp);
    }

    else {
        tree tmp = ask(p * 2 + 1, B[p * 2].max, ty);
        tmp = B[p * 2] + tmp;
        update(B[p], tmp);
    }
}

void change(int x, int p, UL To, int ty)
{
    if(!ty) {
        if(A[p].l == A[p].r && A[p].l == x) {
            A[p].hs = A[p].max = A[p].minstk = To;
            return;
        }

        int mid = A[p].l + A[p].r >> 1;
        if(x <= mid) change(x, p * 2, To, ty);
        else change(x, p * 2 + 1, To, ty);
    }

    else {
        if(B[p].l == B[p].r && B[p].l == x) {
            B[p].hs = B[p].max = B[p].minstk = To;
            return;
        }

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

    if(!ty) {
        tree tmp = ask(p * 2 + 1, A[p * 2].max, ty);
        tmp = A[p * 2] + tmp;
        update(A[p], tmp);
    }

    else {
        tree tmp = ask(p * 2 + 1, B[p * 2].max, ty);
        tmp = B[p * 2] + tmp;
        update(B[p], tmp);
    }
}

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, n, 1, 0);
    build(1, m, 1, 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);
        if(op == 2) x = m - x + 1, change(x, 1, y, 1);
        if(B[1].hs == A[1].hs) cout << "YES\n";
        else cout << "NO\n"; 
    }

}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 8524kb

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: 27ms
memory: 8540kb

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: 27ms
memory: 8476kb

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: 32ms
memory: 8532kb

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 123rd words differ - expected: 'YES', found: 'NO'