QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#841760#9774. Same SumarcaWA 326ms35856kbC++203.1kb2025-01-04 02:05:552025-01-04 02:05:56

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2025-01-04 02:05:56]
  • 评测
  • 测评结果:WA
  • 用时:326ms
  • 内存:35856kb
  • [2025-01-04 02:05:55]
  • 提交

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";
        }
    }
}

详细

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]