QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#290373#7782. Ursa Minorucup-team2307WA 540ms15888kbC++206.3kb2023-12-24 21:56:592023-12-24 21:56:59

Judging History

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

  • [2023-12-24 21:56:59]
  • 评测
  • 测评结果:WA
  • 用时:540ms
  • 内存:15888kb
  • [2023-12-24 21:56:59]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
const ll inf = 1ll<<30;

struct Seg {
    int n;
    vector<int> tr;
    Seg(int N) : n(N), tr(2*N) {}
    void upd(int pos, int val) {
        for(tr[pos+=n]=val;pos/=2;)
            tr[pos] = __gcd(tr[2*pos], tr[2*pos+1]);
    }
    int qry(int l, int r) {
        int res = 0;
        for(l += n, r += n; l < r; l>>=1,r>>=1) {
            if(l & 1) res = __gcd(res, tr[l++]);
            if(r & 1) res = __gcd(res, tr[--r]);
        }
        return res;
    }
};

const int C = 512, mod = 998244853;
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a + mod - b : a - b; }
int mul(int a, int b) { return a*1ll*b%mod; }
struct RSQ1 {//cosnt update root query
    int n;
    vector<int> a, b;
    RSQ1(int N = 0) : n(N), a(n), b(n / C + 1) {}
    void update(int pos, int val) {
        b[pos / C] = sub(b[pos / C], a[pos]);
        b[pos / C] = add(b[pos / C], a[pos] = val);
    }
    int qry(int l, int r) {
        ++r;
        int ans = 0;
        while(l < r) {
            if(l % C == 0 && l + C <= r) {
                ans = add(ans, b[l / C]);
                l += C;
            } else {
                ans = add(ans, a[l++]);
            }
        }
        return ans;
    }
};

struct RSQ2 {//root update const query
    int n;
    vector<int> a, b, c;
    RSQ2(int N = 0) : n(N), a(n), b(n/C+1), c(n) {}
    void update(int pos, int val) {
        for(int i = pos / C + 1; i < b.size(); i++) {
            b[i] = sub(b[i], a[pos]);
            b[i] = add(b[i], val);
        }
        int lim = min((pos / C) * C + C, n);
        for(int i = pos; i < lim; i++) {
            c[i] = sub(c[i], a[pos]);
            c[i] = add(c[i], val);
        }
        a[pos] = val;
    }
    int qry(int r) {
        if(r < 0) return 0;
        int bl = r / C;
        return add(b[bl], c[r]);
    }
    int qry(int l, int r) { return sub(qry(r), qry(l - 1)); }
};

mt19937 rng(123);//!!
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    // {
    //     int n = 20;
    //     RSQ1 a(n);
    //     RSQ2 b(n);
    //     for(int i = 0; i < n; i++) {
    //         a.update(i, i); b.update(i, i);
    //     }
    //     // cout << b.c[1] << b.b[0] << " " << b.qry(0, 1) << endl;
    //     for(int i = 0; i < n; i++) {
    //         for(int j = i; j < n; j++) {
    //             int x = a.qry(i, j), y = b.qry(i, j);
    //             // cout << i << " " << j << " " << x << " " << y << endl;
    //             assert(x == y);
    //             assert(x == j*(j+1)/2 - i*(i-1) / 2);
    //         }
    //     }
    //     return 0;
    // }
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(n);
    for(auto &i : a) cin >> i;
    vector<int> b(m);
    for(auto &i : b) cin >> i;

    Seg gst(m);
    for(int i = 0; i < m; i++) {
        gst.upd(i, b[i]);
    }

    vector<array<int, 5>> queries;
    vector<int> ans(q, 1);
    for(int I = 0; I < q; I++) {
        char type;
        cin >> type;
        if(type == 'Q') {
            int l, r, s, t;
            cin >> l >> r >> s >> t;
            queries.push_back({0, l, r, s, t});
        } else {
            ans[I] = -1;
            int p, v;
            cin >> p >> v;
            queries.push_back({1, p, v, 0, 0});
        }
    }
    //hash stuff
    auto solve = [=, &ans](int x) mutable -> void {
        vector<int> pws(n + 1, 1);
        for(int i = 1; i <= n; i++) pws[i] = pws[i - 1] * 1ll * x % mod;
        auto suf = pws;
        suf.back() = 0;
        for(int i = n; i--;) suf[i] += suf[i + 1];

        vector<RSQ1> small(C);
        for(int i = 1; i < C; i++) {
            small[i] = RSQ1(n);
            for(int j = 0; j < n; j++) {
                small[i].update(j, a[j] * 1ll * pws[j % i] % mod);
            }
        }
        // cout << small[3].qry(0, 5) << " " << a[0] * pws[0] <<endl;
        RSQ2 r2(n);
        RSQ2 S(n);
        for(int i = 0; i < n; i++) {
            r2.update(i, a[i] * 1ll * pws[i]);
            S.update(i, a[i]);
        }
        int ID = -1;
        for(auto Q : queries) { ++ID;
            if(Q[0] == 0) {
                auto [_, l, r, s, t] = Q;
                int G = gst.qry(--s, t);
                G = __gcd(G, r-- - --l);
                // vector<int> sm(G);
                // for(int i = l; i < r; i++) {
                //     sm[i % G] += a[i];
                // }

                int sum = 0;
                if(G < C) {
                    sum = small[G].qry(l, r);
                    sum = mul(sum, pws[n - G]);
                } else {
                    while(l + G < r) {
                        sum = add(sum, mul(r2.qry(l, l + G - 1), pws[(n - G) - l]));
                    }
                    int P = n - G;
                    while(l < r) {
                        sum = add(sum, mul(r2.a[l++], pws[P++]));
                    }
                }

                int real_sum = S.qry(l, r);

                int div = suf[n - G];
                ans[ID] &= real_sum % G == 0 && sum == mul(div, real_sum / G); 


                // cout << G << " " << x << " : " << l << " " << r << " " << sum << " " << div << " " << (real_sum%G) << " " << ID<< endl;
                // for(auto i : sm) cout << i << " "; cout << endl;
                // int ok = *min_element(all(sm)) == *max_element(all(sm));
                // cout << (ok?"Yes\n":"No\n");
            } else {
                auto [_, p, v, __, ___] = Q;
                // a[--p] = v;
                --p;
                for(int i = 1; i < C; i++) {
                    small[i].update(p, mul(v, pws[p % i]));
                }
                r2.update(p, mul(v, pws[p]));
                S.update(p, v);
                a[p] = v;
            }
        }
    };
    // solve(10);
    solve(rng() % (mod - 1) + 1);
    solve(rng() % (mod - 1) + 1);
    // solve(rng() % (mod - 1) + 1);
    for(auto i : ans) if(i >= 0) cout << (i ? "Yes" : "No") << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3712kb

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: 0ms
memory: 3616kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: -100
Wrong Answer
time: 540ms
memory: 15888kb

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 376th words differ - expected: 'Yes', found: 'No'