QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#594363#9302. Caesar Cipherzqx#WA 1437ms109824kbC++233.7kb2024-09-27 22:10:542024-09-27 22:10:54

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:10:54]
  • 评测
  • 测评结果:WA
  • 用时:1437ms
  • 内存:109824kb
  • [2024-09-27 22:10:54]
  • 提交

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 << 2];

    #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;
            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;
            (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();
    }
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 25632kb

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: 10ms
memory: 21884kb

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: 10ms
memory: 24708kb

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: 196ms
memory: 47068kb

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: 1437ms
memory: 107700kb

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: 1206ms
memory: 109804kb

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: 1213ms
memory: 109752kb

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: 1065ms
memory: 109824kb

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]