QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#911 | #591780 | #9302. Caesar Cipher | ship2077 | lonelywolf | Success! | 2024-09-26 18:55:56 | 2024-09-26 18:55:56 |
Details
Extra Test:
Wrong Answer
time: 7ms
memory: 11400kb
input:
100 1 17 0 0 0 3 1 3 18 11 4 5 3 6 4 0 0 5 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 10 0 1 17 0 0 0 0 0 0 0 0 0 0 7 6 13 0 0 13 6 7 0 0 0 0 0 0 0 0 0 0 17 1 0 10 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 5 0 0 4 6 3 5 4 11 18 3 1 3 0 0 0 17 2 1 51 50
output:
yes
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#591780 | #9302. Caesar Cipher | lonelywolf | WA | 1362ms | 59924kb | C++20 | 5.7kb | 2024-09-26 17:46:29 | 2024-09-26 18:56:22 |
answer
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 500000;
constexpr int B = 516;
constexpr array<int, 2> mod = {998244353, 1000000007};
using ll = long long;
int p[N + 10][2];
int s[N + 10][2];
void init() {
p[0][0] = p[0][1] = 1;
s[1][0] = s[1][1] = 1;
for (int t = 0; t < 2; t++) {
for (int i = 1; i <= N; i++) {
p[i][t] = 1LL * p[i - 1][t] * B % mod[t];
s[i + 1][t] = (p[i][t] + s[i][t]) % mod[t];
}
}
}
template<class Info, class Tag>
struct LazySegmentTree {
int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(vector(n_ + 1, v_));
}
template<class T>
void init(vector<T> init_) {
n = init_.size() - 1;
info.assign(4 << __lg(n) + 1, Info());
tag.assign(4 << __lg(n) + 1, Tag());
function<void(int, int, int)> build = [&](int p, int l, int r) {
if (l == r) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m + 1, r);
pull(p);
};
build(1, 1, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (l == r) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x <= m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m + 1, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 1, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l > y || r < x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m + 1, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 1, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l > y || r < x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m + 1, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 1, n, l, r, v);
}
void work(int p, int l, int r) {
if (info[p].mx != 65536) {
return;
}
if (l == r) {
info[p].work();
return;
}
int m = (l + r) / 2;
push(p);
work(2 * p, l, m);
work(2 * p + 1, m + 1, r);
pull(p);
}
template<class F>
int findFirst(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(info[p])) {
return -1;
}
if (l == r) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m + 1, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F pred) {
return findFirst(1, 1, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F pred) {
if (l > y || r < x || !pred(info[p])) {
return -1;
}
if (l == r) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m + 1, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F pred) {
return findLast(1, 1, n, l, r, pred);
}
};
struct Tag {
int d = 0;
void apply(Tag t) {
d += t.d;
}
};
struct Info {
array<int, 2> val {0, 0};
int len = 0;
int mx = 0;
void apply(Tag t) {
mx += t.d;
for (int i = 0; i < 2; i++) {
val[i] = (1LL * t.d * s[len][i] % mod[i] + val[i]) % mod[i];
}
}
void work() {
mx = 0;
val = {0, 0};
}
};
Info operator+(Info a, Info b) {
Info ret;
ret.len = a.len + b.len;
ret.mx = max(a.mx, b.mx);
for (int t = 0; t < 2; t++) {
ret.val[t] = (1LL * a.val[t] * p[b.len][t] % mod[t] + b.val[t]) % mod[t];
}
return ret;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int n, q;
cin >> n >> q;
LazySegmentTree<Info, Tag> tr(n);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
tr.modify(i, {{x % mod[0], x % mod[1]}, 1, x});
}
while (q--) {
int o;
cin >> o;
if (o == 1) {
int l, r;
cin >> l >> r;
tr.rangeApply(l, r, {1});
tr.work(1, 1, n);
} else {
int x, y, L;
cin >> x >> y >> L;
auto v1 = tr.rangeQuery(x, min(n, x + L - 1));
auto v2 = tr.rangeQuery(y, min(n, y + L - 1));
if (v1.val == v2.val && v1.len == v2.len) {
cout << "yes\n";
} else {
cout << "no\n";
}
}
}
return 0;
}