QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#1022 | #642842 | #9302. Caesar Cipher | ship2077 | Ashbourne | Success! | 2024-10-21 09:47:30 | 2024-10-21 09:47:30 |
Details
Extra Test:
Wrong Answer
time: 0ms
memory: 7632kb
input:
101 1 0 0 0 0 0 6 16 32 33 33 51 51 51 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 67 85 108 108 119 119 119 119 119 139 145 157 165 65371 0 8 20 26 46 46 46 46 46 57 57 80 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 98 114 114 114 132 132 133 ...
output:
yes
result:
wrong answer expected NO, found YES [1st token]
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642842 | #9302. Caesar Cipher | Ashbourne | WA | 908ms | 33676kb | C++20 | 4.3kb | 2024-10-15 16:33:47 | 2024-10-21 09:48:00 |
answer
#include<bits/stdc++.h>
#define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
#define drp(i, j, k) for(int i = j; i >= k; -- i)
#define pii pair<int, int>
using namespace std;
const int N = 5e5 + 10;
const int Mod = 65536, M1 = 998244353, M2 = 1e9 + 7;
// #define ls(x) (x << 1)
// #define rs(x) (x << 1 | 1)
// struct SGT {
// pii tr[N << 2];
// void upd (int x) {
// tr[x] = tr[ls(x)] + tr[rs(x)];
// }
// void build(int x, int l, int r, vector<int> &in) {
// if (l == r) return tr[x] = in[l - 1], void();
// int mid = (l + r) >> 1;
// build (ls(x), l, mid, in);
// build (rs(x), mid + 1, r, in);
// upd (x);
// }
// void modify(int x, int l, int r, int cur, int val){
// if(l == r){
// tr[x] = tr[x] + val;
// return;
// }
// int mid = (l + r) >> 1;
// if(cur <= mid) modify(ls(x), l, mid, cur, val);
// else modify(rs(x), mid + 1, r, cur, val);
// upd(x);
// }
// int query(int x, int l, int r, int L, int R) {
// if (L <= l && r <= R) return tr[x];
// int mid = (l + r) >> 1;
// if (R <= mid) return query(ls(x), l, mid, L, R);
// if (L > mid) return query(rs(x), mid + 1, r, L, R);
// return query(ls(x), l, mid, L, R) + query(rs(x), mid + 1, r, L, R);
// }
// } Tr;
int fpow(int a, int b, int M){
int x = 1;
while(b){
if(b & 1)x = x * a % M;
a = a * a % M;
b >>= 1;
}
return x;
}
struct BST{
int tot, Mod;
void resize(int n, int m){
tot = n;
Mod = m;
}
int tr[N << 1];
void init(){
memset(tr, 0, sizeof tr);
}
void add(int x, int num){
if(x == 0) return;
while(x <= tot){
tr[x] += num;
tr[x] %= Mod;
x += x & (-x);
}
}
int query(int x){
int ans = 0;
while(x){
ans += tr[x];
ans %= Mod;
x -= x & (-x);
}
return ans;
}
}bst, tr1, tr2;
void solve(){
int n, q;
cin >> n >> q;
// cout << n << q << endl;
bst.resize(n, Mod);
vector<int> a(n + 1), b(n + 1), w1(n + 1), w2(n + 1);
for(int i = 1; i <= n; ++ i){
cin >> a[i];
}
bst.add(1, a[1]);
rep(i, 1, n - 1) b[i] = (a[i + 1] - a[i] + Mod) % Mod, bst.add(i + 1, b[i]);
int p1 = 70067, p2 = 70379;
tr1.resize(n - 1, M1);
tr2.resize(n - 1, M2);
w1[1] = w2[1] = 1;
for(int i = 1; i <= n - 1; ++ i){
w1[i + 1] = w1[i] * p1 % M1;
w2[i + 1] = w2[i] * p2 % M2;
tr1.add(i, w1[i] * b[i] % M1);
tr2.add(i, w2[i] * b[i] % M2);
}
while(q--){
int cc; cin >> cc;
if(cc == 2){
int x, y, len;
cin >> x >> y >> len;
int a1 = bst.query(x), a2 = bst.query(y);
if(a1 != a2){
cout << "no" << endl;
continue;
}
int hs1 = tr1.query(x + len - 2) + M1 - tr1.query(x - 1);
hs1 %= M1; hs1 = hs1 * fpow(w1[x], M1 - 2, M1) % M1;
int hs2 = tr2.query(x + len - 2) + M2 - tr2.query(x - 1);
hs2 %= M2; hs2 = hs2 * fpow(w2[x], M2 - 2, M2) % M2;
int hs3 = tr1.query(y + len - 2) + M1 - tr1.query(y - 1);
hs3 %= M1; hs3 = hs3 * fpow(w1[y], M1 - 2, M1) % M1;
int hs4 = tr2.query(y + len - 2) + M2 - tr2.query(y - 1);
hs4 %= M2; hs4 = hs4 * fpow(w2[y], M2 - 2, M2) % M2;
// cout << hs1 << " " << hs3 << endl;
// cout << fpow(w1[y], M1 - 2, M1) * w1[y] % M1 << endl;
if(hs1 == hs3 && hs2 == hs4){
cout << "yes" << endl;
}else cout << "no" << endl;
}else{
int l, r;
cin >> l >> r;
bst.add(l, 1); bst.add(r + 1, Mod - 1);
if(l != 1){
b[l - 1] ++;
tr1.add(l - 1, w1[l - 1] % M1);
tr2.add(l - 1, w2[l - 1] % M2);
if(b[l - 1] >= Mod){
b[l - 1] -= Mod;
tr1.add(l - 1, (M1 - Mod) * w1[l - 1] % M1);
tr2.add(l - 1, (M2 - Mod) * w2[l - 1] % M2);
}
}
if(r != n){
b[r] --;
tr2.add(r, w2[r] * (M2 - 1) % M2);
tr1.add(r, w1[r] * (M1 - 1) % M1);
if(b[r] < 0){
b[r] += Mod;
tr2.add(r, w2[r] * (Mod) % M2);
tr1.add(r, w1[r] * (Mod) % M1);
}
}
}
}
}
signed main(){
ios::sync_with_stdio(0);
int T = 1;
// cin >> T;
while(T--){
solve();
}
}