QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#318561 | #7782. Ursa Minor | Network_Error | WA | 72ms | 249508kb | C++20 | 5.8kb | 2024-01-31 14:36:19 | 2024-01-31 14:36:19 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define deb(var) cerr << #var << '=' << (var) << "; "
//#define int long long
namespace IO {
#define BF 65536
char buf[BF], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BF, stdin), p1 == p2) ? EOF : *p1++)
// template<typename T>
inline int uread() {
int x = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return x;
}
// template<typename T>
inline int read() {
int x = 0, f = 0; char c = getchar();
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar(); return f ? -x : x;
}
char obuf[BF + 30]; int o1, o2, num[30];
#define flush() fwrite(obuf, 1, o1, stdout), o1 = 0
inline void putchar(const char &c) {
obuf[o1++] = c; if (o1 >= BF) flush();
}
// template<typename T>
inline void uwrite(int x) {
do num[++o2] = x % 10; while (x /= 10);
do obuf[o1++] = num[o2] ^ 48; while (--o2); obuf[o1++] = '\n'; if (o1 >= BF) flush();
}
// template<typename T>
inline void write(const int& x) {
if (x < 0) obuf[o1++] = '-', uwrite(-x); else uwrite(x);
}
} using namespace IO;
const long long mod = 10000000000000793ll;
#define ll long long
inline long long mul(long long x, long long y, long long mo) {
long long t = x * y - (long long)((long double)x / mo * y + 1e-9) * mo; return t < 0 ? t + mo : t;
}
struct Type {
ll x;
Type() { x = 0; }
Type(int y) { x = y == mod ? 0 : y; }
Type(ll y) { x = y == mod ? 0 : y; }
friend Type operator + (Type a, Type b) {
return Type(a.x + b.x >= mod ? a.x + b.x - mod : a.x + b.x);
}
friend Type operator * (Type a, Type b) {
return Type(mul(a.x, b.x, mod));
}
friend Type operator - (Type a, Type b) {
return a + Type(mod - b.x);
}
friend void operator += (Type& a, Type b) {
a = a + b;
}
friend bool operator == (Type a, Type b) {
return a.x == b.x;
}
friend bool operator != (Type a, Type b) {
return a.x != b.x;
}
};
namespace Maths {
Type power(Type x, int y) {
Type ans = Type(1); while (y) {
if (y & 1) ans = ans * x; y >>= 1; x = x * x;
} return ans;
}
Type inv(Type x) {
return Type(power(x.x, mod - 2));
}
} using namespace Maths;
namespace Loser {
int n, m, q, a[200010], b[200010];
struct stable {
int w[200010][19];
void init() {
for (int i = 1; i <= m; i++) w[i][0] = b[i];
for (int k = 1; k <= 18; k++)
for (int i = 1; i + (1 << k) - 1 <= m; i++) w[i][k] = __gcd(w[i][k - 1], w[i + (1 << (k - 1))][k - 1]);
}
int query(int l, int r) {
int lg = log2(r - l + 1);
return __gcd(w[l][lg], w[r - (1 << lg) + 1][lg]);
}
} st;
const int mxk = 150;
const int siz = 1; const Type x[siz] = {Type(11)};
Type powx[siz][200010], invx[siz][200010], sumx[siz][200010];
const int blk = 500; int tot, bel[200010], L[200010 / blk + 5], R[200010 / blk + 5];
struct block1 { // O(1)? O(sqrt)?
Type w[200010], sum[200010 / blk + 5];
void upd(int p, Type x) {
sum[bel[p]] += x - w[p]; w[p] = x;
}
Type query(int l, int r) {
Type ans = 0;
if (bel[l] == bel[r]) {
for (int i = l; i <= r; i++) ans += w[i]; return ans;
}
for (int i = bel[l] + 1; i < bel[r]; i++) ans += sum[i];
for (int i = l; i <= R[bel[l]]; i++) ans += w[i];
for (int i = L[bel[r]]; i <= r; i++) ans += w[i]; return ans;
}
} b1[mxk + 2][siz];
struct block2 { // O(sqrt)? O(1)?
Type w[200010], b[200010 / blk + 5], pre[200010];
void upd(int p, Type x) {
for (int i = p; i <= R[bel[p]]; i++) pre[i] += x - w[p];
for (int i = bel[p]; i <= tot; i++) b[i] += x - w[p]; w[p] = x;
}
Type query(int r) {
return b[bel[r] - 1] + pre[r];
}
Type query(int l, int r) {
if (l == 1) return query(r);
return query(r) - query(l - 1);
}
} b2[siz];
void upd(int p, Type v) {
for (int k = 1; k <= mxk; k++) {
for (int i = 0; i < siz; i++) {
b1[k][i].upd(p, v * powx[i][p % k]);
}
}
for (int i = 0; i < siz; i++) b2[i].upd(p, v * powx[i][p]);
}
bool query(int l, int r, int k) {
Type sum = b1[1][0].query(l, r);
sum = sum * inv(Type(k));
// if (sum.x % k) return 0; sum.x /= k;
if (k <= mxk) {
for (int i = 0; i < siz; i++) {
if (b1[k][i].query(l, r) != sumx[i][k - 1] * sum) return 0;
} return 1;
} else {
for (int i = 0; i < siz; i++) {
Type ans = 0;
for (int b = l / k; b <= r / k; b++) {
int L = b * k, R = b * k + k - 1;
L = max(L, l); R = min(R, r);
if (L <= R) ans += b2[i].query(L, R) * invx[i][b * k];
}
if (ans != sumx[i][k - 1] * sum) return 0;
} return 1;
}
}
void main() {
n = uread(), m = uread(), q = uread();
for (int i = 1; i <= n; i++) a[i] = uread();
for (int i = 1; i <= m; i++) b[i] = uread();
for (int i = 0; i < siz; i++) {
powx[i][0] = sumx[i][0] = invx[i][0] = 1;
for (int k = 1; k <= 2e5; k++)
powx[i][k] = powx[i][k - 1] * x[i], sumx[i][k] = sumx[i][k - 1] + powx[i][k], invx[i][k] = inv(powx[i][k]);
}
st.init();
for (int i = 1; i <= n; i++) bel[i] = (i - 1) / blk + 1;
tot = bel[n]; for (int i = 1; i <= tot; i++) L[i] = (i - 1) * blk + 1, R[i] = i * blk; R[tot] = n;
for (int i = 1; i <= n; i++) upd(i, a[i]);
while (q--) {
char c = getchar();
while (c != 'U' && c != 'Q') c = getchar();
if (c == 'U') {
int p = uread(), v = uread(); upd(p, v);
} else {
int l = uread(), r = uread(), s = uread(), t = uread(), len = __gcd(st.query(s, t), r - l + 1);
puts(query(l, r, len) ? "Yes" : "No");
}
}
}
}
signed main() { return Loser::main(), 0; }
詳細信息
Test #1:
score: 0
Wrong Answer
time: 72ms
memory: 249508kb
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 No
result:
wrong answer 4th words differ - expected: 'Yes', found: 'No'