QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281097 | #7782. Ursa Minor | ucup-team1191# | TL | 788ms | 36760kb | C++20 | 13.1kb | 2023-12-09 20:58:44 | 2023-12-09 20:58:44 |
Judging History
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 = 2;
const int B = 450;
// const int D = 4;
// const int B = 3;
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 {
#ifdef HOUSE
if ((hu == rhs.hu) != (hm == rhs.hm)) {
cerr << hu << ' ' << rhs.hu << endl;
cerr << hm << ' ' << rhs.hm << endl;
}
#endif
return hu == rhs.hu && hm == rhs.hm;
}
};
OSTREAM(Hash, hu, hm);
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 (int j = 0; j < v.size(); ++j) {
if (j) v[j][0] += v[j - 1].back();
auto& u = v[j];
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--) {
show(block_delta);
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);
// int d = 0;
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3412kb
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: 3568kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 54ms
memory: 3788kb
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: 79ms
memory: 18880kb
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: 66ms
memory: 13396kb
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: 0
Accepted
time: 788ms
memory: 36760kb
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:
ok 187340 tokens
Test #7:
score: -100
Time Limit Exceeded
input:
200000 200000 200000 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531 360543531...
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 ...