QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #290389 | #7782. Ursa Minor | ucup-team2307 | WA | 1058ms | 12796kb | C++20 | 6.7kb | 2023-12-24 22:29:52 | 2023-12-24 22:29:53 |
Judging History
answer
#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back
const ll inf = 1ll<<30;
struct Seg {
int n;
vector<int> tr;
Seg(int N) : n(N), tr(2*N) {}
void upd(int pos, int val) {
for(tr[pos+=n]=val;pos/=2;)
tr[pos] = __gcd(tr[2*pos], tr[2*pos+1]);
}
int qry(int l, int r) {
int res = 0;
for(l += n, r += n; l < r; l>>=1,r>>=1) {
if(l & 1) res = __gcd(res, tr[l++]);
if(r & 1) res = __gcd(res, tr[--r]);
}
return res;
}
};
const int C = 128, mod = 998244853;
int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
int sub(int a, int b) { return a - b < 0 ? a + mod - b : a - b; }
int mul(int a, int b) { return a*1ll*b%mod; }
struct RSQ1 {//cosnt update root query
int n;
vector<int> a, b;
RSQ1(int N = 0) : n(N), a(n), b(n / C + 1) {}
void update(int pos, int val) {
b[pos / C] = sub(b[pos / C], a[pos]);
b[pos / C] = add(b[pos / C], a[pos] = val);
}
int qry(int l, int r) {
++r;
int ans = 0;
while(l < r) {
if(l % C == 0 && l + C <= r) {
ans = add(ans, b[l / C]);
l += C;
} else {
ans = add(ans, a[l++]);
}
}
return ans;
}
};
struct RSQ2 {//root update const query
int n;
vector<int> a, b, c;
RSQ2(int N = 0) : n(N), a(n), b(n/C+1), c(n) {}
void update(int pos, int val) {
for(int i = pos / C + 1; i < b.size(); i++) {
b[i] = sub(b[i], a[pos]);
b[i] = add(b[i], val);
}
int lim = min((pos / C) * C + C, n);
for(int i = pos; i < lim; i++) {
c[i] = sub(c[i], a[pos]);
c[i] = add(c[i], val);
}
a[pos] = val;
}
int qry(int r) {
if(r < 0) return 0;
int bl = r / C;
return add(b[bl], c[r]);
}
int qry(int l, int r) { return sub(qry(r), qry(l - 1)); }
};
mt19937 rng(123);//!!
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
// {
// int n = 20;
// RSQ1 a(n);
// RSQ2 b(n);
// for(int i = 0; i < n; i++) {
// a.update(i, i); b.update(i, i);
// }
// // cout << b.c[1] << b.b[0] << " " << b.qry(0, 1) << endl;
// for(int i = 0; i < n; i++) {
// for(int j = i; j < n; j++) {
// int x = a.qry(i, j), y = b.qry(i, j);
// // cout << i << " " << j << " " << x << " " << y << endl;
// assert(x == y);
// assert(x == j*(j+1)/2 - i*(i-1) / 2);
// }
// }
// return 0;
// }
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n);
for(auto &i : a) cin >> i;
vector<int> b(m);
for(auto &i : b) cin >> i;
Seg gst(m);
for(int i = 0; i < m; i++) {
gst.upd(i, b[i]);
}
vector<array<int, 5>> queries;
vector<int> ans(q, 1);
for(int I = 0; I < q; I++) {
char type;
cin >> type;
if(type == 'Q') {
int l, r, s, t;
cin >> l >> r >> s >> t;
queries.push_back({0, l, r, s, t});
} else {
ans[I] = -1;
int p, v;
cin >> p >> v;
queries.push_back({1, p, v, 0, 0});
}
}
//hash stuff
auto solve = [=, &ans](int x) mutable -> void {
vector<int> pws(2*n + 1, 1);
for(int i = 1; i <= 2*n; i++) pws[i] = pws[i - 1] * 1ll * x % mod;
auto suf = pws;
suf.back() = 0;
for(int i = 2*n; i--;) suf[i] = add(suf[i], suf[i + 1]);
vector<RSQ1> small(C);
for(int i = 1; i < C; i++) {
small[i] = RSQ1(n);
for(int j = 0; j < n; j++) {
small[i].update(j, a[j] * 1ll * pws[j % i] % mod);
}
}
// cout << small[3].qry(0, 5) << " " << a[0] * pws[0] <<endl;
RSQ2 r2(n);
RSQ2 S(n);
for(int i = 0; i < n; i++) {
r2.update(i, a[i] * 1ll * pws[i] % mod);
S.update(i, a[i]);
}
int ID = -1;
int out = 0;
for(auto Q : queries) { ++ID;
if(Q[0] == 0) {
auto [_, l, r, s, t] = Q;
int G = gst.qry(--s, t);
G = __gcd(G, r-- - --l);
if(++out == 376) {
cout << l << " " << r << " " << s << " " << t << " " << G << endl;
}
// vector<int> sm(G);
// for(int i = l; i < r; i++) {
// sm[i % G] += a[i];
// }
int sum = 0;
int real_sum = S.qry(l, r);
if(G < C) {
sum = small[G].qry(l, r);
sum = mul(sum, pws[2*n - G]);
} else {
while(l + G - 1 <= r) {
sum = add(sum, mul(r2.qry(l, l + G - 1), pws[(2*n - G) - l]));
l += G;
}
// cout << sum << endl;
int P = 2*n - G;
while(l <= r) {
sum = add(sum, mul(r2.a[l], pws[P - l]));
l++, P++;
}
}
int div = suf[2*n - G];
ans[ID] &= mul(sum, G) == mul(div, real_sum);
// cout << G << " " << x << " : " << l << " " << r << " " << sum << " " << div << " " << (real_sum) << " " << ID<< endl;
// for(auto i : sm) cout << i << " "; cout << endl;
// int ok = *min_element(all(sm)) == *max_element(all(sm));
// cout << (ok?"Yes\n":"No\n");
} else {
auto [_, p, v, __, ___] = Q;
// a[--p] = v;
--p;
for(int i = 1; i < C; i++) {
small[i].update(p, mul(v, pws[p % i]));
}
r2.update(p, mul(v, pws[p]));
S.update(p, v);
a[p] = v;
}
}
};
solve(10);
// return 0;
solve(rng() % (mod - 1) + 1);
solve(rng() % (mod - 1) + 1);
// solve(rng() % (mod - 1) + 1);
for(auto i : ans) if(i >= 0) cout << (i ? "Yes" : "No") << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3480kb
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: 3512kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: -100
Wrong Answer
time: 1058ms
memory: 12796kb
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:
76 79 3 4 4 76 79 3 4 4 76 79 3 4 4 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 Y...
result:
wrong answer 1st words differ - expected: 'Yes', found: '76'