QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#693235#8338. Quad Kingdoms Chesssnow_mikumikuWA 30ms8544kbC++143.1kb2024-10-31 15:45:282024-10-31 15:45:29

Judging History

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

  • [2024-10-31 15:45:29]
  • 评测
  • 测评结果:WA
  • 用时:30ms
  • 内存:8544kb
  • [2024-10-31 15:45:28]
  • 提交

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 << 2], B[N << 2], nul;

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

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

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

        int mid = l + r >> 1;
        if(B[p * 2].max < mx) 
            return ask(p * 2 + 1, mx, ty, mid + 1, r);
        else {
            tree tmp = ask(p * 2, mx, ty, l, mid);
            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 change(int x, int p, UL To, int ty, int l, int r)
{
    if(!ty) {
        if(l == r) {
            A[p].hs = A[p].max = A[p].minstk = 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);

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

    else {
        if(l == r) {
            B[p].hs = B[p].max = B[p].minstk = 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);

        tree tmp = ask(p * 2 + 1, B[p * 2].max, ty, mid + 1, r);
        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];
        change(i, 1, a[i], 0, 1, n);
    }

    cin >> m;
    for(int i = m; i >= 1; i--) {
        cin >> b[i];
        change(i, 1, b[i], 1, 1, m);
    }

    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: 100
Accepted
time: 1ms
memory: 8464kb

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

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: 26ms
memory: 8524kb

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: 30ms
memory: 8544kb

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
YES
YES
YES
YES
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
...

result:

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