QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#594392 | #9302. Caesar Cipher | zqx# | WA | 1318ms | 110476kb | C++23 | 3.7kb | 2024-09-27 22:56:01 | 2024-09-27 22:56:03 |
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:56:01]
- 提交
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;
ppw[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].mx += v) %= lim;
t[p].hash = t[p].mx + 1;
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;
sgt1.Init(mod1);
sgt2.Init(mod2);
while(T--)
{
Solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 13ms
memory: 24860kb
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: 8ms
memory: 22180kb
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: 0
Accepted
time: 14ms
memory: 25636kb
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:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes ...
result:
ok 1000 token(s): yes count is 1000, no count is 0
Test #4:
score: 0
Accepted
time: 180ms
memory: 45848kb
input:
100000 100000 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:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes ...
result:
ok 100000 token(s): yes count is 100000, no count is 0
Test #5:
score: 0
Accepted
time: 1318ms
memory: 110476kb
input:
500000 500000 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:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes ...
result:
ok 500000 token(s): yes count is 500000, no count is 0
Test #6:
score: 0
Accepted
time: 1146ms
memory: 108372kb
input:
500000 500000 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:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes ...
result:
ok 500000 token(s): yes count is 500000, no count is 0
Test #7:
score: 0
Accepted
time: 1159ms
memory: 110448kb
input:
500000 500000 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 65535 65534 6553...
output:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes no no no yes yes yes yes yes yes yes yes yes yes yes yes yes no yes ...
result:
ok 500000 token(s): yes count is 449947, no count is 50053
Test #8:
score: -100
Wrong Answer
time: 1093ms
memory: 110412kb
input:
500000 500000 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 49999 49997 4999...
output:
yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes yes no yes yes yes yes yes yes yes yes yes yes yes yes yes no yes yes yes yes yes no yes yes yes yes yes yes yes yes yes no yes no yes y...
result:
wrong answer expected YES, found NO [47038th token]