QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1021 | #644282 | #9302. Caesar Cipher | ship2077 | castc | Success! | 2024-10-21 09:39:32 | 2024-10-21 09:39:32 |
Details
Extra Test:
Wrong Answer
time: 3ms
memory: 7756kb
input:
41 1 0 15 15 15 31 34 41 41 41 41 41 41 41 43 43 43 43 63 67 67 65469 0 0 4 24 24 24 24 26 26 26 26 26 26 26 33 36 52 52 52 67 2 1 22 20
output:
yes
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#644282 | #9302. Caesar Cipher | castc | WA | 1335ms | 87276kb | C++20 | 5.3kb | 2024-10-16 12:44:26 | 2024-10-21 09:40:14 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define int long long
template<class Info, class Tag>
struct LazySegmentTree {
const int n;
vector<Info> info;
vector<Tag> tag;
LazySegmentTree(int n) : n(n), info(4 << __lg(n)), tag(4 << __lg(n)) {}
LazySegmentTree(vector<Info> init) : LazySegmentTree(init.size()) {
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, 0, n - 1);
}
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, 0, n - 1, 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) {
if(l > r) return Info();
return rangeQuery(1, 0, n - 1, 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, 0, n - 1, l, r, v);
}
void half(int p, int l, int r) {
if (info[p].act == 0) {
return;
}
if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
apply(p, {-(info[p].min + 1) / 2});
return;
}
int m = (l + r) / 2;
push(p);
half(2 * p, l, m);
half(2 * p + 1, m + 1, r);
pull(p);
}
void half() {
half(1, 0, n - 1);
}
};
const int mod = 1247493647;
const int P = 65536;
const int N = 5e5 + 9;
int pw[N];
struct Tag {
ll add = 0;
void apply(Tag t) {
add += t.add;
}
};
struct Info {
int ans = 0, add = 0, g = 0, sum = 0;
void apply(Tag t) {
ans += t.add * add % mod;
sum += t.add * g;
}
};
Info operator+(Info a, Info b) {
Info c;
if(a.add == 0) return b;
if(b.add == 0) return a;
c.sum = (a.sum + b.sum) % P;
c.ans = (a.ans * pw[b.g] + b.ans) % mod;
c.add = (a.add * pw[b.g] + b.add) % mod;
c.g = a.g + b.g;
return c;
}
void solve() {
pw[0] = 1;
for(int i = 1; i < N; i++) {
pw[i] = pw[i - 1] * 131;
pw[i] %= mod;
}
int n, q;
cin >> n >> q;
vector<Info> init(n);
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
init[i].add = 1;
init[i].g = 1;
}
for(int i = 0; i < n; i++) {
if(i == 0) b[i] = a[i];
else b[i] = a[i] - a[i - 1];
b[i] += P;
b[i] %= P;
init[i].sum = init[i].ans = b[i];
}
LazySegmentTree<Info, Tag> seg(init);
while(q--) {
int op;
cin >> op;
if(op == 1) {
int l, r;
cin >> l >> r;
l--;
auto p = seg.rangeQuery(l, l);
p.ans++;
p.ans %= P;
p.sum = p.ans;
seg.modify(l, p);
if(r < n) {
p = seg.rangeQuery(r, r);
p.ans--;
p.ans += P;
p.ans %= P;
p.sum = p.ans;
seg.modify(r, p);
}
} else {
int x, y, L;
cin >> x >> y >> L;
x--, y--;
int flag = seg.rangeQuery(x + 1, x + L - 1).ans;
flag -= seg.rangeQuery(y + 1, y + L - 1).ans;
if(flag != 0) {
cout << "no\n";
} else {
if(seg.rangeQuery(0, x).sum == seg.rangeQuery(0, y).sum) {
cout << "yes\n";
} else {
cout << "no\n";
}
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
// cin >> T;
while(T--) solve();
return 0;
}