QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#594397 | #9302. Caesar Cipher | zqx# | WA | 1259ms | 110456kb | C++23 | 3.7kb | 2024-09-27 23:01:21 | 2024-09-27 23:01:23 |
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 23:01:21]
- 提交
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int lim = 65536;
const int base = 233;
const int mod1 = 1e9 + 9;
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 25768kb
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: 22016kb
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: 13ms
memory: 24940kb
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: 178ms
memory: 44444kb
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: 1259ms
memory: 108324kb
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: 1070ms
memory: 110456kb
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: 1089ms
memory: 110440kb
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: 1029ms
memory: 110432kb
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]