QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#841760 | #9774. Same Sum | arca | WA | 326ms | 35856kb | C++20 | 3.1kb | 2025-01-04 02:05:55 | 2025-01-04 02:05:56 |
Judging History
answer
/**
我操什么东西这是
*/
#include <cmath>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
using namespace std;
using i64 = long long;
// constexpr i64 M = 998244353;
constexpr double eps = 1e-9;
struct Node {
double Mp, Mm;
i64 sum, len;
i64 tg;
Node(double a = 0, double b = 0, i64 c = 0, i64 d = 0, i64 e = 0) {
Mp = a, Mm = b, sum = c, len = d, tg = e;
}
Node operator+(const Node &a) {
Node tmp(Mp, Mm, sum, len, tg);
tmp.Mp += a.Mp, tmp.Mm += a.Mm, tmp.sum += a.sum, tmp.len += a.len;
return tmp;
}
};
vector<Node> tr;
uniform_int_distribution<i64> gen(1e7, 1e18);
mt19937 rng(random_device());
int n, q;
i64 B;
vector<double> a;
void pullup(int p) {
int ls = p * 2, rs = p * 2 + 1;
tr[p].Mp = tr[ls].Mp + tr[rs].Mp;
tr[p].Mm = tr[ls].Mm + tr[rs].Mm;
tr[p].len = tr[ls].len + tr[rs].len;
tr[p].sum = tr[ls].sum + tr[rs].sum;
}
void MakeTag(int p, int l, int r, double tg) {
double mul = exp(1.0 * tg), ivmul = 1.0 / mul;
tr[p].tg += tg;
tr[p].sum += tg * (r - l + 1);
tr[p].Mp *= mul;
tr[p].Mm *= ivmul;
}
void pushdown(int p, int l, int r) {
if (!tr[p].tg) return;
int ls = p * 2, rs = p * 2 + 1;
int mid = midpoint(l, r);
MakeTag(ls, l, mid, tr[p].tg);
MakeTag(rs, mid + 1, r, tr[p].tg);
tr[p].tg = 0;
}
void Build(int p = 1, int l = 0, int r = n - 1) {
if (l == r) {
tr[p].Mp = exp(a[l]), tr[p].Mm = 1.0 / tr[p].Mp;
tr[p].sum = (i64)a[l], tr[p].len = 1;
tr[p].tg = 0;
return;
}
int mid = midpoint(l, r);
Build(p * 2, l, mid);
Build(p * 2 + 1, mid + 1, r);
pullup(p);
}
void Modify(int ql, int qr, double v, int p = 1, int l = 0,
int r = n - 1) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
MakeTag(p, l, r, v);
return;
}
pushdown(p, l, r);
int mid = midpoint(l, r);
Modify(ql, qr, v, p * 2, l, mid);
Modify(ql, qr, v, p * 2 + 1, mid + 1, r);
pullup(p);
}
Node Query(int ql, int qr, int p = 1, int l = 0, int r = n - 1) {
if (qr < l || r < ql) return Node();
if (ql <= l && r <= qr) return tr[p];
pushdown(p, l, r);
int mid = midpoint(l, r);
Node s;
s = s + Query(ql, qr, p * 2, l, mid);
s = s + Query(ql, qr, p * 2 + 1, mid + 1, r);
return s;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
B = 2;
a.resize(n);
tr.resize(n << 2);
for (auto &i : a) cin >> i;
Build();
int op, l, r;
double w;
while (q--) {
cin >> op >> l >> r;
l--, r--;
if (op == 1) {
cin >> w;
Modify(l, r, w);
} else {
Node s = Query(l, r);
double fp = exp(2.0 * s.sum / s.len);
// std::cout << s.sum << " " << fp << "\n";
if (s.sum % (s.len / 2) == 0 && fabs(s.Mm * fp - s.Mp) <= eps)
cout << "YES\n";
else cout << "NO\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4004kb
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: 326ms
memory: 35856kb
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]