QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594352 | #9302. Caesar Cipher | zqx# | WA | 11ms | 15188kb | C++23 | 3.7kb | 2024-09-27 22:02:33 | 2024-09-27 22:02:34 |
Judging History
你现在查看的是最新测评结果
- [2024-11-04 17:10:09]
- hack成功,自动添加数据
- (/hack/1110)
- [2024-10-21 09:47:48]
- hack成功,自动添加数据
- (/hack/1022)
- [2024-10-21 09:39:50]
- hack成功,自动添加数据
- (/hack/1021)
- [2024-10-21 09:31:34]
- hack成功,自动添加数据
- (/hack/1020)
- [2024-10-03 10:14:59]
- hack成功,自动添加数据
- (/hack/928)
- [2024-09-28 07:51:27]
- hack成功,自动添加数据
- (/hack/922)
- [2024-09-28 07:42:39]
- hack成功,自动添加数据
- (/hack/921)
- [2024-09-27 22:02:33]
- 提交
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int lim = 65536;
const int base = 13331;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
int n;
int a[N];
int pw[N], ppw[N];
struct Segment_Tree
{
static const int N = 5e5 + 10;
int mod;
void Init(int x)
{
mod = x;
pw[0] = 1;
for (int i = 1; i < N; i++)
{
pw[i] = pw[i - 1] * base % mod;
(ppw[i] = ppw[i - 1] + pw[i]) %= mod;
}
}
struct node {
int l, r;
int hash, mx;
int lazy;
}t[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
void Pushup(int p)
{
t[p].mx = max(t[ls(p)].mx, t[rs(p)].mx);
t[p].hash = (t[ls(p)].hash * pw[t[rs(p)].r - t[rs(p)].l + 1] % mod + t[rs(p)].hash) % mod;
}
void Build(int p, int l, int r)
{
t[p].l = l, t[p].r = r;
if (l == r) {
t[p].hash = a[l] + 1;
return ;
}
int mid = (l + r) >> 1;
Build(ls(p), l, mid);
Build(rs(p), mid + 1, r);
Pushup(p);
}
void Pushdown(int p)
{
int lz = t[p].lazy;
if (lz == 0)
return ;
t[ls(p)].lazy += lz;
t[rs(p)].lazy += lz;
(t[ls(p)].hash += lz * ppw[t[ls(p)].r - t[ls(p)].l] % mod) %= mod;
(t[rs(p)].hash += lz * ppw[t[rs(p)].r - t[rs(p)].l] % mod) %= mod;
t[p].lazy = 0;
}
void Update(int p, int l, int r, int v)
{
if (t[p].l == t[p].r)
{
(t[p].hash += v) %= lim;
(t[p].mx += v) %= lim;
return ;
}
if (l <= t[p].l && r >= t[p].r)
{
if (t[p].mx < lim - 1)
{
t[p].lazy += v;
(t[p].hash += v * ppw[t[p].r - t[p].l] % mod) %= mod;
return ;
}
}
Pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
if (l <= mid)
Update(ls(p), l, r, v);
if (r > mid)
Update(rs(p), l, r, v);
Pushup(p);
}
int Query(int p, int l, int r)
{
if (l <= t[p].l && r >= t[p].r)
{
return t[p].hash;
}
Pushdown(p);
int mid = (t[p].l + t[p].r) >> 1;
int res = 0;
if (l > mid)
res = Query(rs(p), l, r);
else if(r <= mid)
res = Query(ls(p), l, r);
else
res = (Query(ls(p), l, mid) * pw[r - mid] % mod + Query(rs(p), mid + 1, r)) % mod;
return res;
}
}sgt1, sgt2;
void Solve()
{
int q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
sgt1.Build(1, 1, n);
sgt2.Build(1, 1, n);
while (q--)
{
int opt;
cin >> opt;
if (opt == 1)
{
int l, r;
cin >> l >> r;
sgt1.Update(1, l, r, 1);
sgt2.Update(1, l, r, 1);
}
else
{
int l1, r1, l2, r2, len;
cin >> l1 >> l2 >> len;
r1 = l1 + len - 1; r2 = l2 + len - 1;
bool ok1 = (sgt1.Query(1, l1, r1) == sgt1.Query(1, l2, r2));
bool ok2 = (sgt2.Query(1, l1, r1) == sgt2.Query(1, l2, r2));
cout << ((ok1 && ok2) ? "yes\n" : "no\n");
}
}
return ;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
sgt1.Init(mod1);
sgt2.Init(mod2);
while(T--)
{
Solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 13904kb
input:
5 6 1 2 1 2 1 2 1 2 2 2 1 3 3 1 1 1 1 3 5 2 1 2 4 2 1 2 2
output:
no yes no yes
result:
ok 4 token(s): yes count is 2, no count is 2
Test #2:
score: 0
Accepted
time: 11ms
memory: 15188kb
input:
3 3 0 65535 65535 2 1 2 2 1 2 3 2 1 2 2
output:
no yes
result:
ok 2 token(s): yes count is 1, no count is 1
Test #3:
score: -100
Wrong Answer
time: 7ms
memory: 14508kb
input:
1000 1000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
no no no no no no 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 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 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 yes no no yes no no no yes no no no no no ...
result:
wrong answer expected YES, found NO [1st token]