QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #279403 | #7782. Ursa Minor | ucup-team1447# | WA | 83ms | 411100kb | C++14 | 6.4kb | 2023-12-08 17:45:40 | 2023-12-08 17:45:41 |
Judging History
answer
// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
// #define debug
const int B = 10;
const int MOD = 1000000009;
const int base = 1000000001;
struct mint
{
unsigned v;
mint(unsigned v_ = 0) : v(v_) {}
mint operator-() const { return v ? MOD - v : *this; }
mint &operator+=(const mint &X) { return (v += X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator-=(const mint &X) { return (v += MOD - X.v) >= MOD ? v -= MOD : v, *this; }
mint &operator*=(const mint &X) { return v = 1llu * v * X.v % MOD, *this; }
mint &operator/=(const mint &X) { return *this *= X.inv(); }
mint pow(long long B) const
{
B %= MOD - 1;
if (B < 0)
B += MOD - 1;
mint res = 1, A = *this;
while (B)
{
if (B & 1)
res *= A;
B >>= 1;
A *= A;
}
return res;
}
mint inv() const { return pow(MOD - 2); }
friend mint operator+(const mint &A, const mint &B) { return mint(A) += B; }
friend mint operator-(const mint &A, const mint &B) { return mint(A) -= B; }
friend mint operator*(const mint &A, const mint &B) { return mint(A) *= B; }
friend mint operator/(const mint &A, const mint &B) { return mint(A) /= B; }
friend std::istream &operator>>(std::istream &A, mint &B) { return A >> B.v; }
friend std::ostream &operator<<(std::ostream &A, const mint &B) { return A << B.v; }
friend bool operator==(const mint &A, const mint &B) { return A.v == B.v; }
explicit operator bool() const { return v; }
} a[200005], c[200005], sump[405][505][505], sumh[405][505], sum[405][505], pw[200005];
int n, m, q, b[200005];
int gcd[1 << 19];
#define lson (now << 1)
#define rson (now << 1 | 1)
#define lmid ((l + r) >> 1)
#define rmid (lmid + 1)
void pushup(int now) { gcd[now] = std::__gcd(gcd[lson], gcd[rson]); }
void build(int now = 1, int l = 1, int r = m)
{
if (l == r)
{
gcd[now] = b[l];
return;
}
build(lson, l, lmid);
build(rson, rmid, r);
pushup(now);
}
int query(int L, int R, int now = 1, int l = 1, int r = m)
{
if (R < l || r < L)
return 0;
if (L <= l && r <= R)
return gcd[now];
return std::__gcd(query(L, R, lson, l, lmid), query(L, R, rson, rmid, r));
}
void init()
{
for (int i = 0; i != n; ++i)
c[i] = a[i] - (i ? a[i - 1] : 0);
for (int i = 0; i * B != n; ++i)
{
for (int j = 1; j <= B; ++j)
{
for (int k = i * B; k != (i + 1) * B; ++k)
sump[i][j][k % j] += c[k];
for (int k = 0; k != j; ++k)
sumh[i][j] += pw[k] * sump[i][j][k];
}
for (int j = B; j--;)
sum[i][j] = sum[i][j + 1] * base + c[i * B + j];
}
}
void add(int pos, mint val)
{
if (pos == n)
return;
int in = pos / B;
for (int i = 1; i <= B; ++i)
{
sump[in][i][pos % i] += val;
sumh[in][i] += pw[pos % i] * val;
}
c[pos] += val;
for (int j = B; j--;)
sum[in][j] = sum[in][j + 1] * base + c[in * B + j];
}
mint get_first(int l, int r, int dis)
{
int p = l % dis;
mint res = 0;
if (dis <= B)
{
while (l % B && l != r)
{
if (l % dis == p)
res += c[l];
++l;
}
while (l / B != r / B)
{
res += sump[l / B][dis][p];
l += B;
}
while (l != r)
{
if (l % dis == p)
res += c[l];
++l;
}
}
else
{
while (l != r)
{
res += c[l];
l += dis;
}
}
return res;
}
mint get_sum(int l, int r, int dis)
{
mint res = 0;
if (dis <= B)
{
while (l % B && l != r)
{
res += c[l] * pw[l % dis];
++l;
}
while (l / B != r / B)
{
res += sumh[l / B][dis];
l += B;
}
while (l != r)
{
res += c[l] * pw[l % dis];
++l;
}
}
else
{
while (l % B && l != r)
{
res += c[l] * pw[l % dis];
++l;
}
while (l / B != r / B)
{
int sp = std::min(dis - l % dis, B);
res += (sum[l / B][0] - sum[l / B][sp] * pw[sp]) * pw[l % dis];
res += sum[l / B][sp];
l += B;
}
while (l != r)
{
res += c[l] * pw[l % dis];
++l;
}
}
return res;
}
mint get_first_(int l, int r, int dis)
{
mint res = 0;
while (l != r)
{
res += c[l];
l += dis;
}
return res;
}
mint get_sum_(int l, int r, int dis)
{
mint res = 0;
while (l != r)
{
res += c[l] * pw[l % dis];
++l;
}
return res;
}
signed main()
{
// freopen("data.in", "r", stdin);
std::ios::sync_with_stdio(false);
pw[0] = 1;
for (int i = 1; i <= 200000; ++i)
pw[i] = pw[i - 1] * base;
std::cin >> n >> m >> q;
for (int i = 0; i != n; ++i)
std::cin >> a[i];
while (n % B)
++n;
for (int i = 1; i <= m; ++i)
std::cin >> b[i];
build();
init();
for (int i = 1; i <= q; ++i)
{
static char opt;
static int l, r, s, t, p, v;
std::cin >> opt;
if (opt == 'U')
{
std::cin >> p >> v;
--p;
add(p, v - a[p]);
add(p + 1, a[p] - v);
a[p] = v;
}
if (opt == 'Q')
{
std::cin >> l >> r >> s >> t;
--l;
int gcd = std::__gcd(r - l, query(s, t));
// for (int j = 2; j <= r - l; ++j)
// if ((r - l) % j == 0)
// {
// gcd = (r - l) / j;
// break;
// }
mint f = get_first(l, r, gcd) * pw[l % gcd], g = get_sum(l, r, gcd);
// mint f_ = get_first_(l, r, gcd) * pw[l % gcd], g_ = get_sum_(l, r, gcd);
// // std::cout << l << ' ' << r << ' ' << gcd << ' ' << g << ' ' << g_ << std::endl;
// assert(f == f_ && g == g_);
std::cout << (g == f ? "Yes" : "No") << std::endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 32ms
memory: 411012kb
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: 19ms
memory: 411072kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: -100
Wrong Answer
time: 83ms
memory: 411100kb
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 60956th words differ - expected: 'No', found: 'Yes'