QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#280823 | #7782. Ursa Minor | ucup-team1198# | WA | 1267ms | 27640kb | C++14 | 7.3kb | 2023-12-09 17:59:23 | 2023-12-09 17:59:23 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int K = 179;
const int MAXN = 400400;
int n;
long long fenw[MAXN];
void add_fenw(int i, long long x) {
for (; i < 2 * n; i = (i | (i + 1)))
fenw[i] += x;
}
long long get(int i) {
long long ans = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
ans += fenw[i];
return ans;
}
long long get(int l, int r) {
return get(r - 1) - get(l - 1);
}
int gcd(int a, int b) {
while (b) {
a %= b;
swap(a, b);
}
return a;
}
int tree_gcd[(1 << 19) + 228];
void build(int v, int left, int right, vector<int>& A) {
if (left + 1 == right) {
tree_gcd[v] = A[left];
return;
}
int mid = (left + right) / 2;
build(2 * v + 1, left, mid, A);
build(2 * v + 2, mid, right, A);
tree_gcd[v] = gcd(tree_gcd[2 * v + 1], tree_gcd[2 * v + 2]);
}
int get_gcd(int v, int left, int right, int x, int y) {
if (y <= left || right <= x)
return 0;
if (x <= left && right <= y)
return tree_gcd[v];
int mid = (left + right) / 2;
return gcd(get_gcd(2 * v + 1, left, mid, x, y), get_gcd(2 * v + 2, mid, right, x, y));
}
const int MOD1 = 1e9 + 9;
int add1(int a, int b) {
return a + b >= MOD1 ? a + b - MOD1 : a + b;
}
int sub1(int a, int b) {
return a >= b ? a - b : a + MOD1 - b;
}
int mul1(int a, int b) {
return (1ll * a * b) % MOD1;
}
const int MOD2 = 1e9 + 447;
int add2(int a, int b) {
return a + b >= MOD2 ? a + b - MOD2 : a + b;
}
int sub2(int a, int b) {
return a >= b ? a - b : a + MOD2 - b;
}
int mul2(int a, int b) {
return (1ll * a * b) % MOD2;
}
const int BASE = 379;
int BASEPOW1[MAXN];
int BASEPOW2[MAXN];
pair<int, int> combine(pair<int, int> A, pair<int, int> B, int r_len) {
return make_pair(add1(mul1(A.first, BASEPOW1[r_len]), B.first),
add2(mul2(A.second, BASEPOW2[r_len]), B.second));
}
const pair<int, int> NONE(0, 0);
pair<int, int> cur_vals[MAXN];
pair<int, int> suff_hashes[MAXN];
pair<int, int> pref_hashes[MAXN];
pair<int, int> get_segm_hash(int left, int right) {
int l = left / K + 1;
int r = right / K;
pair<int, int> ans = suff_hashes[left];
for (int i = l; i < r; ++i)
ans = combine(ans, suff_hashes[i * K], K);
ans = combine(ans, pref_hashes[right], right - r * K + 1);
return ans;
}
void recalc_block(int id) {
id /= K;
pair<int, int> cur_pref = NONE;
for (int i = id * K; i < id * K + K; ++i) {
cur_pref = combine(cur_pref, cur_vals[i], 1);
pref_hashes[i] = cur_pref;
}
pair<int, int> cur_suff = NONE;
for (int i = id * K + K - 1; i >= id * K; --i) {
cur_suff = combine(cur_vals[i], cur_suff, id * K + K - i - 1);
suff_hashes[i] = cur_suff;
}
}
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif
BASEPOW1[0] = 1;
for (int i = 1; i < MAXN; ++i)
BASEPOW1[i] = mul1(BASEPOW1[i - 1], BASE);
BASEPOW2[0] = 1;
for (int i = 1; i < MAXN; ++i)
BASEPOW2[i] = mul1(BASEPOW2[i - 1], BASE);
int m, q;
cin >> n >> m >> q;
vector<long long> A(n);
for (int i = 0; i < n; ++i)
cin >> A[i];
vector<int> B(m);
for (int i = 0; i < m; ++i)
cin >> B[i];
build(0, 0, m, B);
vector<pair<pair<int, int>, int>> queries(q);
vector<int> interesting;
for (int i = 0; i < q; ++i) {
char c;
cin >> c;
if (c == 'U') {
int p, v;
cin >> p >> v;
--p;
queries[i] = make_pair(make_pair(p, v), -1);
} else {
int l, r, s, t;
cin >> l >> r >> s >> t;
--l;
--r;
--s;
--t;
int k = gcd(r - l + 1, get_gcd(0, 0, m, s, t + 1));
if (k <= K)
interesting.emplace_back(k);
queries[i] = make_pair(make_pair(l, r), k);
}
}
vector<bool> ans(q);
sort(interesting.begin(), interesting.end());
interesting.resize(unique(interesting.begin(), interesting.end()) - interesting.begin());
vector<long long> cur_a;
for (int k : interesting) {
cur_a = A;
fill(fenw, fenw + 2 * n, 0);
auto get_real_id = [k](int i) {
return (i % k) * (n / k + 1) + i / k;
};
for (int i = 0; i < n; ++i) {
add_fenw(get_real_id(i), cur_a[i] - (i == 0 ? 0 : cur_a[i - 1]));
}
for (int j = 0; j < q; ++j) {
if (queries[j].second == -1) {
// upd
int i = queries[j].first.first;
int x = queries[j].first.second;
add_fenw(get_real_id(i), x - cur_a[i]);
if (i + 1 < n)
add_fenw(get_real_id(i + 1), cur_a[i] - x);
cur_a[i] = x;
} else if (queries[j].second == k) {
// query
int l = queries[j].first.first;
int r = queries[j].first.second;
ans[j] = true;
for (int i = 1; i < k; ++i) {
// l + i
long long cur_sum = get(get_real_id(l + i), get_real_id(r + 1 - k + i) + 1);
if (cur_sum != 0)
ans[j] = false;
}
long long cur_sum = get(get_real_id(l), get_real_id(r + 1 - k) + 1) + (l == 0 ? 0 : cur_a[l - 1]) - cur_a[r];
if (cur_sum != 0)
ans[j] = false;
}
}
}
for (int i = 0; i < n; ++i) {
cur_vals[i].first = (A[i] - (i == 0 ? 0 : A[i - 1]) + MOD1) % MOD1;
cur_vals[i].second = (A[i] - (i == 0 ? 0 : A[i - 1]) + MOD2) % MOD2;
}
for (int i = 0; i < n; i += K)
recalc_block(i);
cur_a = A;
for (int j = 0; j < q; ++j) {
if (queries[j].second == -1) {
// upd
int i = queries[j].first.first;
int x = queries[j].first.second;
cur_vals[i].first = add1(cur_vals[i].first, (x - cur_a[i] + MOD1) % MOD1);
cur_vals[i].second = add2(cur_vals[i].second, (x - cur_a[i] + MOD2) % MOD2);
if (i + 1 < n) {
cur_vals[i + 1].first = add1(cur_vals[i + 1].first, (cur_a[i] - x + MOD2) % MOD2);
cur_vals[i + 1].second = add2(cur_vals[i + 1].second, (cur_a[i] - x + MOD2) % MOD2);
}
cur_a[i] = x;
recalc_block(i);
if ((i + 1) / K != i / K)
recalc_block(i + 1);
} else if (queries[j].second > K) {
// query
int l = queries[j].first.first;
int r = queries[j].first.second;
int k = queries[j].second;
pair<int, int> total_hash = NONE;
for (int i = l; i < r; i += k) {
auto tmp = get_segm_hash(i, i + k - 1);
total_hash.first = add1(total_hash.first, tmp.first);
total_hash.second = add2(total_hash.second, tmp.second);
}
int delta = (l == 0 ? 0 : cur_a[l - 1]) - cur_a[r];
total_hash.first = add1(total_hash.first, mul1((delta + MOD1) % MOD1, BASEPOW1[k - 1]));
total_hash.second = add2(total_hash.second, mul2((delta + MOD2) % MOD2, BASEPOW2[k - 1]));
ans[j] = total_hash == NONE;
}
}
for (int i = 0; i < q; ++i) {
if (queries[i].second != -1) {
if (ans[i])
cout << "Yes\n";
else
cout << "No\n";
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 13896kb
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: 3ms
memory: 15940kb
input:
1 1 1 0 1 Q 1 1 1 1
output:
Yes
result:
ok "Yes"
Test #3:
score: 0
Accepted
time: 262ms
memory: 16240kb
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: 231ms
memory: 19244kb
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: 200ms
memory: 19028kb
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: -100
Wrong Answer
time: 1267ms
memory: 27640kb
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:
wrong answer 128593rd words differ - expected: 'Yes', found: 'No'