QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340714#7782. Ursa MinorgoodierWA 640ms20900kbC++176.1kb2024-02-29 11:29:382024-02-29 11:29:39

Judging History

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

  • [2024-02-29 11:29:39]
  • 评测
  • 测评结果:WA
  • 用时:640ms
  • 内存:20900kb
  • [2024-02-29 11:29:38]
  • 提交

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];
                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];
            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();
	int cnt = 0;
    for(int i = 1; i <= q; i++)
    {
        if(qr[i].op == 0)
        {
            if(ans[i]) write1();
            else write0();
			cnt++;
			if(cnt == 480) exit(qr[i].k > T);
        }
    }
    return 0;
}

详细

Test #1:

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

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: 3ms
memory: 20000kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: -100
Wrong Answer
time: 640ms
memory: 20900kb

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
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
No
Yes
No
No
No
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
No...

result:

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