QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594377 | #9302. Caesar Cipher | zqx# | WA | 7ms | 25232kb | C++23 | 3.7kb | 2024-09-27 22:31:34 | 2024-09-27 22:31: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:31:34]
- 提交
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];
struct Segment_Tree
{
static const int N = 5e5 + 10;
int mod;
int pw[N], ppw[N];
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 << 3];
#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;
t[p].mx=a[l];
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)].mx+=lz;
t[rs(p)].mx+=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+1;
(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();
}
}
详细
Test #1:
score: 100
Accepted
time: 7ms
memory: 25232kb
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: -100
Wrong Answer
time: 7ms
memory: 23900kb
input:
3 3 0 65535 65535 2 1 2 2 1 2 3 2 1 2 2
output:
no no
result:
wrong answer expected YES, found NO [2nd token]