QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#844019 | #9774. Same Sum | arca | WA | 574ms | 59348kb | C++20 | 4.9kb | 2025-01-05 11:51:07 | 2025-01-05 11:51:07 |
Judging History
answer
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using i64 = long long;
bool isPrime(i64 n) {
if (n == 1) return false;
for (i64 i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int n, q;
i64 M, P, iP, P2, iP2;
std::uniform_int_distribution<i64> RNG(1e5, 1e6), RNG2(1e5, 1e6);
std::mt19937_64 mt(std::random_device{}());
i64 fpow(i64 a, i64 b, i64 p = M) {
i64 res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
struct Node {
i64 Mp, Mm;
i64 Mp2, Mm2;
i64 sum, len;
i64 tag;
Node(i64 Mp = 0, i64 Mm = 0, i64 Mp2 = 0, i64 Mm2 = 0, i64 sum = 0,
i64 len = 0, i64 tag = 0)
: Mp(Mp),
Mm(Mm),
Mp2(Mp2),
Mm2(Mm2),
sum(sum),
len(len),
tag(tag) {}
Node operator+(const Node &rhs) const {
return Node((Mp + rhs.Mp) % M,
(Mm + rhs.Mm) % M,
(Mp2 + rhs.Mp2) % M,
(Mm2 + rhs.Mm2) % M,
sum + rhs.sum,
len + rhs.len,
tag + rhs.tag);
}
};
std::vector<Node> T;
std::vector<i64> a;
void pullup(int p) {
T[p].Mp = (T[p << 1].Mp + T[p << 1 | 1].Mp) % M;
T[p].Mm = (T[p << 1].Mm + T[p << 1 | 1].Mm) % M;
T[p].Mp2 = (T[p << 1].Mp2 + T[p << 1 | 1].Mp2) % M;
T[p].Mm2 = (T[p << 1].Mm2 + T[p << 1 | 1].Mm2) % M;
T[p].sum = T[p << 1].sum + T[p << 1 | 1].sum;
T[p].len = T[p << 1].len + T[p << 1 | 1].len;
}
void maketag(int p, int l, int r, i64 v, i64 Pv, i64 iPv, i64 P2v,
i64 iP2v) {
T[p].sum += v * (r - l + 1);
T[p].Mp = T[p].Mp * Pv % M;
T[p].Mm = T[p].Mm * iPv % M;
T[p].Mp2 = T[p].Mp2 * P2v % M;
T[p].Mm2 = T[p].Mm2 * iP2v % M;
T[p].tag += v;
}
void pushdown(int p, int l, int r, i64 v, i64 Pv, i64 iPv, i64 P2v,
i64 iP2v) {
if (!T[p].tag) return;
int mid = std::midpoint(l, r);
maketag(p << 1, l, mid, v, Pv, iPv, P2v, iP2v);
maketag(p << 1 | 1, mid + 1, r, v, Pv, iPv, P2v, iP2v);
T[p].tag = 0;
}
void Build(int p = 1, int l = 0, int r = n - 1) {
if (l == r) {
T[p] = Node(fpow(P, a[l]),
fpow(iP, a[l]),
fpow(P2, a[l]),
fpow(iP2, a[l]),
a[l],
1,
0);
return;
}
int mid = std::midpoint(l, r);
Build(p << 1, l, mid);
Build(p << 1 | 1, mid + 1, r);
pullup(p);
}
void Modify(int ql, int qr, i64 v, i64 Pv, i64 iPv, i64 P2v, i64 iP2v,
int p = 1, int l = 0, int r = n - 1) {
if (ql <= l && r <= qr) {
maketag(p, l, r, v, Pv, iPv, P2v, iP2v);
return;
}
int mid = std::midpoint(l, r);
// pushdown(p,
// l,
// r,
// T[p].tag,
// fpow(P, T[p].tag),
// fpow(iP, T[p].tag),
// fpow(P2, T[p].tag),
// fpow(iP2, T[p].tag));
if (ql <= mid) Modify(ql, qr, v, Pv, iPv, P2v, iP2v, p << 1, l, mid);
if (qr > mid)
Modify(ql, qr, v, Pv, iPv, P2v, iP2v, p << 1 | 1, mid + 1, r);
pullup(p);
}
Node query(int ql, int qr, int p = 1, int l = 0, int r = n - 1) {
if (ql <= l && r <= qr) return T[p];
int mid = std::midpoint(l, r);
pushdown(p,
l,
r,
T[p].tag,
fpow(P, T[p].tag),
fpow(iP, T[p].tag),
fpow(P2, T[p].tag),
fpow(iP2, T[p].tag));
if (qr <= mid) return query(ql, qr, p << 1, l, mid);
else if (ql > mid) return query(ql, qr, p * 2 + 1, mid + 1, r);
else
return query(ql, qr, p << 1, l, mid) +
query(ql, qr, p * 2 + 1, mid + 1, r);
}
int main() {
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
P = RNG(mt), M = RNG2(mt), P2 = RNG(mt);
while (!isPrime(P)) P++;
while (!isPrime(M)) M++;
while (!isPrime(P2)) P2++;
iP = fpow(P, M - 2, M);
iP2 = fpow(P2, M - 2, M);
std::cin >> n >> q;
T.resize(n * 5);
a.resize(n);
for (int i = 0; i < n; i++) std::cin >> a[i];
Build();
while (q--) {
int op, l, r;
std::cin >> op >> l >> r;
if (op == 1) {
i64 x;
std::cin >> x;
Modify(l - 1,
r - 1,
x,
fpow(P, x),
fpow(iP, x),
fpow(P2, x),
fpow(iP2, x));
} else {
auto res = query(l - 1, r - 1);
auto fp = fpow(P, res.sum / (res.len / 2));
if (res.Mp % M == res.Mm * fp % M) std::cout << "YES\n";
else std::cout << "NO\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3620kb
input:
8 4 1 2 3 4 5 6 7 8 2 1 8 1 1 4 4 2 1 6 2 1 8
output:
YES NO YES
result:
ok 3 token(s): yes count is 2, no count is 1
Test #2:
score: -100
Wrong Answer
time: 574ms
memory: 59348kb
input:
200000 200000 0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...
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 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 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 NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
wrong answer expected YES, found NO [464th token]