QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#594372	#9302. Caesar Cipher	zqx^#	WA	1740ms	110464kb	C++23	4.2kb	2024-09-27 22:22:55	2024-09-27 22:22:55

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:22:55]
评测

测评结果：WA
用时：1740ms
内存：110464kb

查看

[2024-09-27 22:22:55]
提交

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;
            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 ;
        if (t[p].l == t[p].r)
        {
            (t[p].hash += t[p].lazy) %= lim;
            (t[p].mx += t[p].lazy) %= lim;
            return ;
        }
        if (t[ls(p)].mx + lz < lim)
        {
            (t[ls(p)].hash += lz * ppw[t[ls(p)].r - t[ls(p)].l] % mod) %= mod;
            t[ls(p)].lazy += lz;
            t[ls(p)].mx += lz;
        }
        else 
        {
            t[ls(p)].lazy += lz;
            Pushdown(ls(p));
            Pushup(ls(p));
        }
        if (t[rs(p)].mx + lz < lim)
        {
            (t[rs(p)].hash += lz * ppw[t[rs(p)].r - t[rs(p)].l] % mod) %= mod;
            t[rs(p)].lazy += lz;
            t[rs(p)].mx += lz;
        }
        else 
        {
            t[rs(p)].lazy += lz;
            Pushdown(rs(p));
            Pushup(rs(p));
        }
        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 + v < lim)
            {
                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();
    }
}

源文件, 语言: C++23

详细

Test #1:

score: 100

Accepted

time: 7ms

memory: 25860kb

input:

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: 24628kb

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: 4ms

memory: 25688kb

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: 321ms

memory: 47804kb

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: 1740ms

memory: 110328kb

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: 1447ms

memory: 110332kb

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: 1349ms

memory: 110464kb

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: 1180ms

memory: 110336kb

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]