QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#386730 | #7782. Ursa Minor | SamponYW | WA | 570ms | 183564kb | C++14 | 4.5kb | 2024-04-11 19:42:08 | 2024-04-11 19:42:09 |
Judging History
answer
#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
bool pDEB, DEB; int tim;
#define N 200005
const int B = 200;
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
int be[N], L[N], R[N], pw[N];
int n, m, q, a[N], b[N], c[N];
struct sma {
int B, v[N], s[N];
il void build(int k) {
B = k;
FOR(i, 1, n) {
v[i] = 1ll * pw[i % B] * c[i] % P;
addr(s[be[i]], v[i]);
}
}
il void upd(int x, int k) {
k = 1ll * k * pw[x % B] % P;
addr(v[x], k), addr(s[be[x]], k);
}
il int query(int l, int r) {
int a = be[l], b = be[r], ns = 0;
if(a == b) {FOR(i, l, r) addr(ns, v[i]); return ns;}
FOR(i, l, R[a]) addr(ns, v[i]);
FOR(i, a + 1, b - 1) addr(ns, s[i]);
FOR(i, L[b], r) addr(ns, v[i]);
return ns;
}
} T[B + 5];
struct info {
int v, L;
} v[N], s[N], pre[N], suf[N];
il info merge(info A, info B) {
return {(A.v + 1ll * pw[A.L] * B.v) % P, A.L + B.L};
}
namespace big {
il void reb(int t) {
info k = {0, 0};
FOR(i, L[t], R[t])
k = merge(k, v[i]), pre[i] = k;
s[t] = k, k = {0, 0};
ROF(i, R[t], L[t])
k = merge(v[i], k), suf[i] = k;
}
il void build() {
FOR(i, 1, n) v[i] = {c[i], 1};
FOR(i, 1, be[n]) reb(i);
}
il void upd(int x, int k) {addr(v[x].v, k), reb(be[x]);}
il info query(int l, int r) {
// if(DEB) cout << "query=" << l << "+" << r << ",";
if(l > r) return {0, 0}; info k = {0, 0};
if(be[l] == be[r]) {
// if(DEB) cout << "brt,";
FOR(i, l, r) k = merge(k, v[i]); return k;}
// if(DEB) cout << "nb,";
k = merge(k, suf[l]);
FOR(i, be[l] + 1, be[r] - 1) k = merge(k, s[i]);
k = merge(k, pre[r]); return k;
}
}
il void upd(int x, int k) {
int d = (k - c[x] + P) % P; c[x] = k;
FOR(i, 1, B) T[i].upd(x, d); big::upd(x, d);
}
namespace rmq {
int st[20][N];
il void build() {
FOR(i, 1, m) st[0][i] = b[i];
FOR(i, 1, 19) FOR(j, 1, m - (1 << i) + 1)
st[i][j] = __gcd(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
il int query(int l, int r) {
int t = __lg(r - l + 1);
return __gcd(st[t][l], st[t][r - (1 << t) + 1]);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
FOR(i, 1, n) cin >> a[i];
pDEB = n == 2e5 && a[1] == 793134805;
FOR(i, 1, n) c[i] = add(a[i % n + 1], P - a[i]);
FOR(i, 1, m) cin >> b[i]; rmq::build();
pw[0] = 1; FOR(i, 1, n) pw[i] = 19260817ll * pw[i - 1] % P;
FOR(i, 1, n) {
be[i] = (i - 1) / B + 1, R[be[i]] = i;
if(be[i] != be[i - 1]) L[be[i]] = i;
}
FOR(i, 1, B) T[i].build(i); big::build();
tim = 0;
while(q--) {
char op; cin >> op;
if(op == 'U') {
int x, v; cin >> x >> v, a[x] = v;
upd(x, add(a[x % n + 1], P - a[x]));
--x; if(!x) x = n;
upd(x, add(a[x % n + 1], P - a[x]));
}
else {
++tim;
DEB = pDEB && tim == 49;
int l, r, s, t; cin >> l >> r >> s >> t;
if(l == r) {cout << "Yes\n"; continue;}
int g = __gcd(r - l + 1, rmq::query(s, t)), ns = 0;
// if(DEB) cout << g << ",";
// if(DEB && tim == 49) cout << g << "," << B << " ";
if(g <= B) ns = add(T[g].query(l, r - 1), 1ll * pw[r % g] * add(a[l], P - a[r]) % P);
else {
while(l + g - 1 <= r - 1) {
auto k = big::query(l, l + g - 1);
addr(ns, k.v), l += g;
}
auto k = big::query(l, r - 1);
// if(DEB) cout << k.L << ",";
// if(k.L != g) k = merge(k, {add(a[l], P - a[r]), 1}), addr(ns, k.v);
// else addr(ns, k.v), addr(ns, add(a[l], P - a[r]));
k = merge(k, {add(a[l], P - a[r]), 1}), addr(ns, k.v);
}
if(DEB) cout << ns << ",";
if(!ns) cout << "Yes\n"; else cout << "No\n";
}
}
cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5688kb
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: 2ms
memory: 5556kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 504ms
memory: 7408kb
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: 184ms
memory: 19408kb
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: 195ms
memory: 14412kb
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: 570ms
memory: 183472kb
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: 0
Accepted
time: 475ms
memory: 183564kb
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 ...
result:
ok 199985 tokens
Test #8:
score: -100
Wrong Answer
time: 457ms
memory: 183520kb
input:
200000 200000 200000 793134805 922104801 158394038 993313213 77527653 992889267 148461787 499165677 132176015 189185554 783374975 332147281 923925325 371040161 393285793 437388761 138662855 212488140 265392646 498903298 578518594 550390771 960084339 408548934 56106823 814997309 456913457 300689692 1...
output:
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 No No No No No No No No No No No No Yes No No No No No No No 886380811,No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No No ...
result:
wrong answer 49th words differ - expected: 'Yes', found: '886380811,No'