QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340723#7782. Ursa MinorgoodierWA 647ms23208kbC++176.0kb2024-02-29 11:32:592024-02-29 11:32:59

Judging History

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

  • [2024-02-29 11:32:59]
  • 评测
  • 测评结果:WA
  • 用时:647ms
  • 内存:23208kb
  • [2024-02-29 11:32:59]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 10, B = 450, T = 450;
const ll MOD = 998244353, base = 34261314;

int f[N][19], len[N], a[N], b[N], ba[N], n, m, q, ans[N], L[N], R[N], pos[N], t;
ll pw[N], spw[N], inv[N], s[N][2][2];

ll power(ll a, ll b)
{
    ll c = 1;
    while(b)
    {
        if(b & 1) c = c * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return c;
}

struct Op{
    int op, l, r, x, y, k;
}qr[N];

int read()
{
    int x = 0, t = 1; char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') t = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * t;
}

void write1()
{
    putchar('Y'), putchar('e'), putchar('s'), putchar('\n');
}

void write0()
{
    putchar('N'), putchar('o'), putchar('\n');
}

int gcd(int a, int b)
{
    while(b)
    {
        int c = a;
        a = b, b = c % b;
    }
    return a;
}

int query(int l, int r)
{
    int t = len[r - l + 1];
    return gcd(f[l][t], f[r - (1 << t) + 1][t]);
}

void init()
{
    for(int i = 2; i <= m; i++) len[i] = len[i >> 1] + 1;
    for(int i = 1; i <= m; i++) f[i][0] = b[i];
    for(int j = 1; j <= len[m]; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= m; i++)
        {
            f[i][j] = gcd(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }

    pw[0] = 1; for(int i = 1; i <= n; i++) pw[i] = pw[i - 1] * (ll)base % MOD; spw[0] = 1; for(int i = 1; i <= n; i++) spw[i] = (spw[i - 1] + pw[i]) % MOD;
    for(int i = 0; i <= n; i++) inv[i] = power(pw[i], MOD - 2);
    t = n / B;
    for(int i = 1; i <= t; i++)
    {
        L[i] = R[i - 1] + 1, R[i] = i * B;
        for(int j = L[i]; j <= R[i]; j++) pos[j] = i;
    }
    if(R[t] < n)
    {
        t++;
        L[t] = R[t - 1] + 1, R[t] = n;
        for(int j = L[t]; j <= R[t]; j++) pos[j] = t;
    }
}

void add1(int x, ll y, int c)
{
    if(y < 0) y += MOD;
    s[x][0][c] += y, s[pos[x]][1][c] += y;
    if(s[x][0][c] >= MOD) s[x][0][c] -= MOD;
    if(s[x][1][c] >= MOD) s[x][1][c] -= MOD;
}

void add2(int x, ll y, int c)
{
    for(int i = x; i <= R[pos[x]]; i++)
    {
        s[i][0][c] += y;
        if(s[i][0][c] >= MOD) s[i][1][c] -= MOD;
    }
    for(int i = pos[x]; i <= t; i++)
    {
        s[i][1][c] += y;
        if(s[i][1][c] >= MOD) s[i][1][c] -= MOD;
    }
}

ll ask2(int x, int c)
{
    if(x == 0) return 0;
    ll res = s[x][0][c] + s[pos[x] - 1][1][c];
    if(res >= MOD) res -= MOD;
    return res;
}

ll ask1(int x, int c)
{
    if(x == 0) return 0;
    ll res = 0;
    for(int i = 1; i < pos[x]; i++)
    {
        res += s[i][1][c];
        if(res >= MOD) res -= MOD;
    }
    for(int i = L[pos[x]]; i <= x; i++)
    {
        res += s[i][0][c];
        if(res >= MOD) res -= MOD;
    }
    return res;
}

ll query1(int l, int r, int c)
{
    return (ask1(r, c) - ask1(l - 1, c) + MOD) % MOD;
}

ll query2(int l, int r, int c)
{
    ll res = ask2(r, c) - ask2(l - 1, c) + MOD;
    if(res >= MOD) res -= MOD;
    return res;
}

void solve1()
{
    for(int k = 1; k <= T; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            a[i] = ba[i]; s[i][0][0] = s[i][0][1] = s[i][1][0] = s[i][1][1] = 0;
        }
        for(int i = 1; i <= n; i++)
        {
            if(i % k == 0) add1(i, a[i], 0);
            add1(i, (ll)a[i] * pw[i % k] % MOD, 1);
        }
        for(int i = 1; i <= q; i++)
        {
            if(qr[i].op == 1)
            {
                int x = qr[i].x, dt = qr[i].y - a[x] + MOD;
                if(x % k == 0) add1(x, dt, 0);
                add1(x, (ll)dt * pw[x % k] % MOD, 1);
                a[x] += dt;
            }
            else if(qr[i].k == k)
            {
                int l = qr[i].l, r = qr[i].r;
                ans[i] = (query1(l, r, 0) * spw[k - 1] % MOD) == query1(l, r, 1);
            }
        }
    }
}

void solve2()
{
    for(int i = 1; i <= n; i++)
    {
        a[i] = ba[i]; s[i][0][0] = s[i][0][1] = s[i][1][0] = s[i][1][1] = 0;
    }
    for(int i = 1; i <= n; i++)
    {
        add2(i, (ll)a[i] * pw[i] % MOD, 0);
    }
    for(int i = 1; i <= q; i++)
    {
        if(qr[i].op == 1)
        {
            int x = qr[i].x, dt = qr[i].y - a[x] + MOD;
            add2(x, (ll)dt * pw[x], 0);
            a[x] += dt;
        }
        else if(qr[i].k > T)
        {
            int k = qr[i].k, l = qr[i].l, r = qr[i].r;
            ll res = 0;
            for(int j = 1; j <= n; j += k)
            {
                int ll = j, rr = min(j + k - 1, n);
                int LL = max(l, ll), RR = min(r, rr);
                if(LL <= RR)
                {
                    res += query2(LL, RR, 0) * inv[j] % MOD;
                    if(res >= MOD) res -= MOD;
                }
            }
            ll s0 = 0;
            for(int j = k; j <= n; j += k)
            {
                if(l <= j && j <= r)
                {
                    s0 += a[j];
                    if(s0 >= MOD) s0 -= MOD;
                }
            }
            ans[i] = (s0 * spw[k - 1] % MOD) == res;
        }
    }
}

int main()
{
    //freopen("data.in", "r", stdin);
    n = read(), m = read(), q = read();
    for(int i = 1; i <= n; i++) ba[i] = a[i] = read();
    for(int i = 1; i <= m; i++) b[i] = read();
    init();
    for(int i = 1; i <= q; i++)
    {
        char str[2]; scanf("%s", str);
        if(str[0] == 'Q')
        {
            int l = read(), r = read(), x = read(), y = read();
            qr[i] = Op({0, l, r, x, y, gcd(r - l + 1, query(x, y))});
        }
        else
        {
            int x = read(), y = read();
            qr[i] = Op({1, 0, 0, x, y});
        }
    }
    solve1();
    solve2();
    for(int i = 1; i <= q; i++)
    {
        if(qr[i].op == 0)
        {
            if(ans[i]) write1();
            else write0();
        }
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 14124kb

input:

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4

output:

Yes
No
No
Yes

result:

ok 4 tokens

Test #2:

score: 0
Accepted
time: 2ms
memory: 18200kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: -100
Wrong Answer
time: 647ms
memory: 23208kb

input:

2000 2000 200000
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 1 2 0 0 2 2 2 1 0 1 2 1 2 0 0 1 1 1 2 0 0 2 2 2 2 0 2 0 0 2 1 2 0 0 1 2 2 1 0 2 0 0 0 1 2 2 1 2 2 0 0 1 1 1 0 0 2 0 0 1 1 0 2 2 2 1 0 0 1 0 1 2 2 2 1 1 2 2 1 2 1 0 2 2 3 1 3 2 3 1 0 1 2 0 1 1 1 0 2 2 3 2 0 3 2 3 3 1 2 3 1 2 0 1 0 3 1 0 0 2 0 1 2 1 3 2 2...

output:

Yes
Yes
No
Yes
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Yes
Yes
No
No
No
No
No
Yes
No
No
No
Yes
Yes
No
Yes
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No
Y...

result:

wrong answer 55th words differ - expected: 'Yes', found: 'No'