QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#281061#7782. Ursa Minorucup-team1191#WA 610ms190200kbC++2012.6kb2023-12-09 20:34:482023-12-09 20:34:48

Judging History

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

  • [2023-12-09 20:34:48]
  • 评测
  • 测评结果：WA
  • 用时：610ms
  • 内存：190200kb
查看
  • [2023-12-09 20:34:48]
  • 提交

answer

/*
    author:  Maksim1744
    created: 09.12.2023 14:51:11
*/

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define mp   make_pair
#define pb   push_back
#define eb   emplace_back

#define sum(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())

template<typename T>             vector<T>& operator--            (vector<T> &v){for (auto& i : v) --i;            return  v;}
template<typename T>             vector<T>& operator++            (vector<T> &v){for (auto& i : v) ++i;            return  v;}
template<typename T>             istream& operator>>(istream& is,  vector<T> &v){for (auto& i : v) is >> i;        return is;}
template<typename T>             ostream& operator<<(ostream& os,  vector<T>  v){for (auto& i : v) os << i << ' '; return os;}
template<typename T, typename U> pair<T,U>& operator--           (pair<T, U> &p){--p.first; --p.second;            return  p;}
template<typename T, typename U> pair<T,U>& operator++           (pair<T, U> &p){++p.first; ++p.second;            return  p;}
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U> &p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> ostream& operator<<(ostream& os, pair<T, U>  p){os << p.first << ' ' << p.second; return os;}
template<typename T, typename U> pair<T,U> operator-(pair<T,U> a, pair<T,U> b){return mp(a.first-b.first, a.second-b.second);}
template<typename T, typename U> pair<T,U> operator+(pair<T,U> a, pair<T,U> b){return mp(a.first+b.first, a.second+b.second);}
template<typename T, typename U> void umin(T& a, U b){if (a > b) a = b;}
template<typename T, typename U> void umax(T& a, U b){if (a < b) a = b;}

#ifdef HOME
#define SHOW_COLORS
#include "/mnt/c/Libs/tools/print.cpp"
#else
#define show(...) void(0)
#define debugf(fun)   fun
#define debugv(var)   var
#define mclock    void(0)
#define shows     void(0)
#define debug  if (false)
#define OSTREAM(...)    ;
#define OSTREAM0(...)   ;
#endif

const int D = 100;
const int B = 450;

template<typename T, typename F = std::function<T(const T&, const T&)>>
struct SparseTable {
    vector<vector<T>> table;
    vector<int> p2;
    F combine;

    SparseTable(int n, F combine) : combine(combine) {
        while ((1 << table.size()) <= n || table.empty())
            table.emplace_back(n);
    }
    template<typename U>
    SparseTable(const vector<U>& v, F combine) : SparseTable<T>(v.size(), combine) {
        table[0].assign(v.begin(), v.end());
        build();
    }

    void build() {
        p2.resize(table[0].size() + 1);
        for (int i = 2; i < p2.size(); ++i)
            p2[i] = p2[i / 2] + 1;
        for (int i = 1; i < table.size(); ++i) {
            for (int j = 0; j + (1 << i) <= table[i].size(); ++j) {
                table[i][j] = combine(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T ask(int l, int r) {
        int ln = p2[r - l + 1];
        if (r - l + 1 == ln) return table[ln][l];
        return combine(table[ln][l], table[ln][r - (1 << ln) + 1]);
    }
};

template<typename T>
struct fenwick {
    vector<T> tree;
    int n;
    int K;

    fenwick(int n = 0) : n(n) {
        tree.assign(n, 0);
        K = 0;
        while ((1 << K) <= n)
            ++K;
    }

    void add(int i, T k) {
        for (; i < n; i = (i | (i + 1)))
            tree[i] += k;
    }

    T ask(int r) {
        T res = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            res += tree[r];
        return res;
    }

    T ask(int l, int r) {
        if (l > r) return 0;
        return ask(r) - ask(l - 1);
    }

    // find first i such that sum[0..i] >= x
    int lower_bound(T x) {
        int cur = 0;
        T cur_sum = 0;
        for (int k = K - 1; k >= 0; --k) {
            int ind = cur | ((1 << k) - 1);
            if (ind >= n) continue;
            if (cur_sum + tree[ind] >= x) continue;
            cur_sum += tree[ind];
            cur |= (1 << k);
        }
        return cur;
    }
};

namespace mint_ns {
template<auto P>
struct Modular {
    using value_type = decltype(P);
    value_type value;

    constexpr Modular(long long k = 0) : value(norm(k)) {}

    friend constexpr Modular<P>& operator += (      Modular<P>& n, const Modular<P>& m) { n.value += m.value; if (n.value >= P) n.value -= P; return n; }
    friend constexpr Modular<P>  operator +  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r += m; }

    friend constexpr Modular<P>& operator -= (      Modular<P>& n, const Modular<P>& m) { n.value -= m.value; if (n.value < 0)  n.value += P; return n; }
    friend constexpr Modular<P>  operator -  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r -= m; }
    friend constexpr Modular<P>  operator -  (const Modular<P>& n)                      { return Modular<P>(-n.value); }

    friend constexpr Modular<P>& operator *= (      Modular<P>& n, const Modular<P>& m) { n.value = n.value * 1ll * m.value % P; return n; }
    friend constexpr Modular<P>  operator *  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r *= m; }

    friend constexpr Modular<P>& operator /= (      Modular<P>& n, const Modular<P>& m) { return n *= m.inv(); }
    friend constexpr Modular<P>  operator /  (const Modular<P>& n, const Modular<P>& m) { Modular<P> r = n; return r /= m; }

    Modular<P>& operator ++ (   ) { return *this += 1; }
    Modular<P>& operator -- (   ) { return *this -= 1; }
    Modular<P>  operator ++ (int) { Modular<P> r = *this; *this += 1; return r; }
    Modular<P>  operator -- (int) { Modular<P> r = *this; *this -= 1; return r; }

    friend constexpr bool operator == (const Modular<P>& n, const Modular<P>& m) { return n.value == m.value; }
    friend constexpr bool operator != (const Modular<P>& n, const Modular<P>& m) { return n.value != m.value; }

    explicit    operator       int() const { return value; }
    explicit    operator      bool() const { return value; }
    explicit    operator long long() const { return value; }

    constexpr static value_type mod()      { return     P; }

    constexpr value_type norm(long long k) {
        if (!(-P <= k && k < P)) k %= P;
        if (k < 0) k += P;
        return k;
    }

    Modular<P> inv() const {
        value_type a = value, b = P, x = 0, y = 1;
        while (a != 0) { value_type k = b / a; b -= k * a; x -= k * y; swap(a, b); swap(x, y); }
        return Modular<P>(x);
    }
};
template<auto P> Modular<P> pow(Modular<P> m, long long p) {
    Modular<P> r(1);
    while (p) {
        if (p & 1) r *= m;
        m *= m;
        p >>= 1;
    }
    return r;
}

template<auto P> ostream& operator << (ostream& o, const Modular<P>& m) { return o << m.value; }
template<auto P> istream& operator >> (istream& i,       Modular<P>& m) { long long k; i >> k; m.value = m.norm(k); return i; }
template<auto P> string   to_string(const Modular<P>& m) { return to_string(m.value); }

using Mint = Modular<1000000007>;
// using Mint = Modular<998244353>;
// using Mint = long double;

vector<Mint> f, fi;
void init_C(int n) {
    f.assign(n, 1); fi.assign(n, 1);
    for (int i = 2; i < n; ++i) f[i] = f[i - 1] * i;
    fi.back() = Mint(1) / f.back();
    for (int i = n - 2; i >= 0; --i) fi[i] = fi[i + 1] * (i + 1);
}
Mint C(int n, int k) {
    if (k < 0 || k > n) return 0;
    else return f[n] * fi[k] * fi[n - k];
}
}
using namespace mint_ns;


const uint64_t PU = 5792438681590757847ull;
const uint64_t PINVU = 640429216751946215ull;
static_assert(PU * PINVU == 1);

constexpr Mint PM = 293749283;
constexpr Mint PINVM = 730384450;
static_assert(PM * PINVM == 1);

struct Hash {
    uint64_t hu = 0;
    Mint hm = 0;

    Hash() = default;
    explicit Hash(uint64_t x) : hu(x), hm(x) {}
    constexpr explicit Hash(uint64_t a, Mint b) : hu(a), hm(b) {}

    Hash operator * (const Hash& rhs) const {
        return Hash(hu * rhs.hu, hm * rhs.hm);
    }
    Hash operator * (uint64_t x) const {
        return Hash(hu * x, hm * x);
    }
    Hash& operator += (const Hash& rhs) {
        hu += rhs.hu;
        hm += rhs.hm;
        return *this;
    }
    Hash& operator -= (const Hash& rhs) {
        hu -= rhs.hu;
        hm -= rhs.hm;
        return *this;
    }
    Hash operator + (const Hash& rhs) const {
        auto h = *this;
        return h += rhs;
    }

    bool operator == (const Hash& rhs) const = default;
};

const Hash P = Hash(PU, PM);
const Hash PINV = Hash(PINVU, PINVM);

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;
    vector<int> a(n);
    cin >> a;
    vector<int> b(m);
    cin >> b;
    SparseTable<int> sparse(b, [](int a, int b) { return gcd(a, b); });
    vector<Hash> pows(n + 5);
    vector<Hash> invpows(n + 5);
    invpows[0] = Hash(1);
    for (int i = 1; i < invpows.size(); ++i)
        invpows[i] = invpows[i - 1] * PINV;
    pows[0] = Hash(1);
    for (int i = 1; i < pows.size(); ++i) {
        pows[i] = pows[i - 1] * P;
    }
    vector<Hash> prefpows = pows;
    for (int i = 1; i < prefpows.size(); ++i)
        prefpows[i] += prefpows[i - 1];
    vector<array<Hash, B>> v(n / B + 1);
    for (auto& u : v)
        u.fill(Hash(0));
    for (int i = 0; i < n; ++i) {
        v[i / B][i % B] = pows[i] * a[i];
    }
    for (auto& u : v)
        for (int i = 1; i < B; ++i)
            u[i] += u[i - 1];
    vector<Hash> block_delta(n / B + 1, Hash(0));

    fenwick<ll> justsum(n);
    for (int i = 0; i < n; ++i) {
        justsum.add(i, a[i]);
    }

    vector<fenwick<ll>> trees;
    trees.pb(0);
    for (int d = 1; d <= D; ++d) {
        trees.pb(n + d + 5);
        for (int i = 0; i < n; ++i) {
            trees.back().add((i % d) * (n / d + 1) + i / d, a[i]);
        }
    }

    while (q--) {
        char c;
        cin >> c;
        if (c == 'U') {
            int ind;
            int val;
            cin >> ind >> val;
            --ind;
            int vdelta = val - a[ind];
            a[ind] = val;
            justsum.add(ind, vdelta);
            Hash delta = pows[ind] * vdelta;
            for (int j = ind % B; j < B; ++j)
                v[ind / B][j] += delta;
            for (int i = ind / B + 1; i < block_delta.size(); ++i)
                block_delta[i] += delta;
            for (int d = 1; d <= D; ++d)
                trees[d].add((ind % d) * (n / d + 1) + ind / d, vdelta);
        } else {
            auto pointval = [&](int i) {
                return v[i / B][i % B] + block_delta[i / B];
            };
            auto segsum = [&](int l, int r) {
                Hash res = pointval(r);
                if (l) res -= pointval(l - 1);
                return res;
            };

            int l, r, s, t;
            cin >> l >> r >> s >> t;
            --l; --r; --s; --t;
            int d = sparse.ask(s, t);
            d = gcd(d, r - l + 1);
            ll sm = justsum.ask(l, r);
            show(l, r, d, sm);
            if (sm % d != 0) {
                cout << "No\n";
                continue;
            }
            sm /= d;
            if (d <= D) {
                ll last = -1;
                bool ok = true;
                for (int rem = 0; rem < d; ++rem) {
                    int li = l + rem;
                    int ri = r + 1 + rem - d;
                    li = (li % d) * (n / d + 1) + li / d;
                    ri = (ri % d) * (n / d + 1) + ri / d;
                    ll cur = trees[d].ask(li, ri);
                    if (rem && last != cur) {
                        ok = false;
                        break;
                    }
                    last = cur;
                }
                cout << (ok ? "Yes" : "No") << '\n';
            } else {
                Hash cur(0);
                for (int i = l; i <= r; i += d) {
                    cur += segsum(i, i+d-1) * invpows[i];
                }
                Hash need = prefpows[d - 1] * sm;
                show(cur);
                show(need);
                cout << (cur == need ? "Yes" : "No") << '\n';
            }
        }
    }

    return 0;
}
源文件, 语言: C++20

详细

Test #1:

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

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: 1ms
memory: 3752kb

input:

1 1 1
0
1
Q 1 1 1 1

output:

Yes

result:

ok "Yes"

Test #3:

score: 0
Accepted
time: 219ms
memory: 4992kb

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:

ok 100554 tokens

Test #4:

score: 0
Accepted
time: 139ms
memory: 19064kb

input:

1 200000 200000
998244353
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

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 100240 tokens

Test #5:

score: 0
Accepted
time: 116ms
memory: 13636kb

input:

6 131072 200000
0 0 0 0 1000000000 1000000000
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...

output:

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

result:

ok 100021 tokens

Test #6:

score: -100
Wrong Answer
time: 610ms
memory: 190200kb

input:

200000 200000 200000
490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877 490339877...

output:

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

result:

wrong answer 682nd words differ - expected: 'Yes', found: 'No'
English 繁體中文 简体中文

服务器时间: 2024-12-12 23:21:08 | 开源项目