QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594379#9302. Caesar Cipherzqx#WA 1156ms110488kbC++233.7kb2024-09-27 22:32:312024-09-27 22:32:31

Judging History

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

  • [2024-11-04 17:10:09]
  • hack成功,自动添加数据
  • (/hack/1110)
  • [2024-10-21 09:47:48]
  • hack成功,自动添加数据
  • (/hack/1022)
  • [2024-10-21 09:39:50]
  • hack成功,自动添加数据
  • (/hack/1021)
  • [2024-10-21 09:31:34]
  • hack成功,自动添加数据
  • (/hack/1020)
  • [2024-10-03 10:14:59]
  • hack成功,自动添加数据
  • (/hack/928)
  • [2024-09-28 07:51:27]
  • hack成功,自动添加数据
  • (/hack/922)
  • [2024-09-28 07:42:39]
  • hack成功,自动添加数据
  • (/hack/921)
  • [2024-09-27 22:32:31]
  • 评测
  • 测评结果:WA
  • 用时:1156ms
  • 内存:110488kb
  • [2024-09-27 22:32:31]
  • 提交

answer

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 5e5 + 10;
const int lim = 65536;
const int base = 13331;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;

int n;
int a[N];

struct Segment_Tree 
{
    static const int N = 5e5 + 10;

    int mod;
    int pw[N], ppw[N];
    void Init(int x)
    {
        mod = x;
        pw[0] = 1;
        for (int i = 1; i < N; i++)
        {
            pw[i] = pw[i - 1] * base % mod;
            (ppw[i] = ppw[i - 1] + pw[i]) %= mod;
        }
    }

    struct node {
        int l, r;
        int hash, mx;
        int lazy;
    }t[N << 3];

    #define ls(x) (x << 1)
    #define rs(x) (x << 1 | 1)

    void Pushup(int p)
    {
        t[p].mx = max(t[ls(p)].mx, t[rs(p)].mx);
        t[p].hash = (t[ls(p)].hash * pw[t[rs(p)].r - t[rs(p)].l + 1] % mod + t[rs(p)].hash) % mod;
    }

    void Build(int p, int l, int r)
    {
        t[p].l = l, t[p].r = r;
        if (l == r) {
            t[p].hash = a[l] + 1;
            t[p].mx=a[l];
            return ;
        }
        int mid = (l + r) >> 1;
        Build(ls(p), l, mid);
        Build(rs(p), mid + 1, r);
        Pushup(p);
    }

    void Pushdown(int p)
    {
        int lz = t[p].lazy;
        if (lz == 0)
           return ;
        t[ls(p)].lazy += lz;
        t[rs(p)].lazy += lz;
        t[ls(p)].mx+=lz;
        t[rs(p)].mx+=lz;
        (t[ls(p)].hash += lz * ppw[t[ls(p)].r - t[ls(p)].l] % mod) %= mod;
        (t[rs(p)].hash += lz * ppw[t[rs(p)].r - t[rs(p)].l] % mod) %= mod;
        t[p].lazy = 0;
    }

    void Update(int p, int l, int r, int v)
    {
        if (t[p].l == t[p].r)
        {
            ((t[p].hash += v) %= lim)+1;
            (t[p].mx += v) %= lim;
            return ;
        }

        if (l <= t[p].l && r >= t[p].r)
        {
            if (t[p].mx < lim - 1)
            {
                t[p].lazy += v;
                (t[p].hash += v * ppw[t[p].r - t[p].l] % mod) %= mod;
                return ;
            }
        }
        Pushdown(p);
        int mid = (t[p].l + t[p].r) >> 1;
        if (l <= mid)
            Update(ls(p), l, r, v);
        if (r > mid)
            Update(rs(p), l, r, v);
        Pushup(p);
    }

    int Query(int p, int l, int r)
    {
        if (l <= t[p].l && r >= t[p].r) 
        {
            return t[p].hash;
        }
        Pushdown(p);
        int mid = (t[p].l + t[p].r) >> 1;
        int res = 0;
        if (l > mid)
            res = Query(rs(p), l, r);
        else if(r <= mid)
            res = Query(ls(p), l, r);
        else 
            res = (Query(ls(p), l, mid) * pw[r - mid] % mod + Query(rs(p), mid + 1, r)) % mod;
        return res;
    }
}sgt1, sgt2;

void Solve()
{
    int q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sgt1.Build(1, 1, n);
    sgt2.Build(1, 1, n);
    while (q--)
    {
        int opt;
        cin >> opt;
        if (opt == 1)
        {
            int l, r;
            cin >> l >> r;
            sgt1.Update(1, l, r, 1);
            sgt2.Update(1, l, r, 1);
        }
        else 
        {
            int l1, r1, l2, r2, len;
            cin >> l1 >> l2 >> len;
            r1 = l1 + len - 1; r2 = l2 + len - 1;
            bool ok1 = (sgt1.Query(1, l1, r1) == sgt1.Query(1, l2, r2));
            bool ok2 = (sgt2.Query(1, l1, r1) == sgt2.Query(1, l2, r2));
            cout << ((ok1 && ok2) ? "yes\n" : "no\n");
        }
    }
    return ;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    // cin >> T;
    sgt1.Init(mod1);
    sgt2.Init(mod2);
    while(T--)
    {
        Solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 13ms
memory: 24316kb

input:

5 6
1 2 1 2 1
2 1 2 2
2 1 3 3
1 1 1
1 3 5
2 1 2 4
2 1 2 2

output:

no
yes
no
yes

result:

ok 4 token(s): yes count is 2, no count is 2

Test #2:

score: 0
Accepted
time: 6ms
memory: 24436kb

input:

3 3
0 65535 65535
2 1 2 2
1 2 3
2 1 2 2

output:

no
yes

result:

ok 2 token(s): yes count is 1, no count is 1

Test #3:

score: 0
Accepted
time: 9ms
memory: 25200kb

input:

1000 1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
...

result:

ok 1000 token(s): yes count is 1000, no count is 0

Test #4:

score: 0
Accepted
time: 159ms
memory: 45920kb

input:

100000 100000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
...

result:

ok 100000 token(s): yes count is 100000, no count is 0

Test #5:

score: 0
Accepted
time: 1156ms
memory: 110488kb

input:

500000 500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
...

result:

ok 500000 token(s): yes count is 500000, no count is 0

Test #6:

score: 0
Accepted
time: 1021ms
memory: 108304kb

input:

500000 500000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
...

result:

ok 500000 token(s): yes count is 500000, no count is 0

Test #7:

score: 0
Accepted
time: 1030ms
memory: 110480kb

input:

500000 500000
65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 6553...

output:

yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
no
no
no
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
yes
no
yes
...

result:

ok 500000 token(s): yes count is 449947, no count is 50053

Test #8:

score: -100
Wrong Answer
time: 981ms
memory: 106352kb

input:

500000 500000
49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 4999...

output:

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
no
no
no
no
no
no
no
no
no
no
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
yes
no
no
no
no...

result:

wrong answer expected YES, found NO [3rd token]