QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#602268#6435. Paimon Segment TreeSusie_RainWA 45ms84100kbC++2012.6kb2024-09-30 22:28:432024-09-30 22:28:45

Judging History

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

  • [2024-09-30 22:28:45]
  • 评测
  • 测评结果：WA
  • 用时：45ms
  • 内存：84100kb
查看
  • [2024-09-30 22:28:43]
  • 提交

answer

#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
//  _____   _   _____    _____   _____   _      __    __
// |  ___| | | |  _  \  | ____| |  ___| | |     \ \  / /
// | |__   | | | |_| |  | |__   | |__   | |      \ \/ /
// |  __|  | | |  _  /  |  __|  |  __|  | |       \  /
// | |     | | | | \ \  | |___  | |     | |___    / /
// |_|     |_| |_|  \_\ |_____| |_|     |_____|  /_/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define lowbit(i) ((i) & -(i))
#define ull unsigned long long
#define int long long
// #define ll long long
#define Genshin_Impact return
#define Starts 0
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e4 + 10;
using i64 = long long;

template <class T>
constexpr T power(T a, i64 b)
{
    T res = 1;
    for (; b; b /= 2, a *= a)
    {
        if (b % 2)
        {
            res *= a;
        }
    }
    return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p)
{
    i64 res = a * b - i64(1.L * a * b / p) * p;
    res %= p;
    if (res < 0)
    {
        res += p;
    }
    return res;
}
template <i64 P>
struct MLong
{
    i64 x;
    constexpr MLong() : x{} {}
    constexpr MLong(i64 x) : x{norm(x % getMod())} {}

    static i64 Mod;
    constexpr static i64 getMod()
    {
        if (P > 0)
        {
            return P;
        }
        else
        {
            return Mod;
        }
    }
    constexpr static void setMod(i64 Mod_)
    {
        Mod = Mod_;
    }
    constexpr i64 norm(i64 x) const
    {
        if (x < 0)
        {
            x += getMod();
        }
        if (x >= getMod())
        {
            x -= getMod();
        }
        return x;
    }
    constexpr i64 val() const
    {
        return x;
    }
    explicit constexpr operator i64() const
    {
        return x;
    }
    constexpr MLong operator-() const
    {
        MLong res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MLong inv() const
    {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MLong &operator*=(MLong rhs) &
    {
        x = mul(x, rhs.x, getMod());
        return *this;
    }
    constexpr MLong &operator+=(MLong rhs) &
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MLong &operator-=(MLong rhs) &
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MLong &operator/=(MLong rhs) &
    {
        return *this *= rhs.inv();
    }
    friend constexpr MLong operator*(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MLong operator+(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MLong operator-(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MLong operator/(MLong lhs, MLong rhs)
    {
        MLong res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MLong &a)
    {
        i64 v;
        is >> v;
        a = MLong(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MLong lhs, MLong rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MLong lhs, MLong rhs)
    {
        return lhs.val() != rhs.val();
    }
};

template <>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template <int P>
struct MInt
{
    int x;
    constexpr MInt() : x{} {}
    constexpr MInt(i64 x) : x{norm(x % getMod())} {}

    static int Mod;
    constexpr static int getMod()
    {
        if (P > 0)
        {
            return P;
        }
        else
        {
            return Mod;
        }
    }
    constexpr static void setMod(int Mod_)
    {
        Mod = Mod_;
    }
    constexpr int norm(int x) const
    {
        if (x < 0)
        {
            x += getMod();
        }
        if (x >= getMod())
        {
            x -= getMod();
        }
        return x;
    }
    constexpr int val() const
    {
        return x;
    }
    explicit constexpr operator int() const
    {
        return x;
    }
    constexpr MInt operator-() const
    {
        MInt res;
        res.x = norm(getMod() - x);
        return res;
    }
    constexpr MInt inv() const
    {
        assert(x != 0);
        return power(*this, getMod() - 2);
    }
    constexpr MInt &operator*=(MInt rhs) &
    {
        x = 1LL * x * rhs.x % getMod();
        return *this;
    }
    constexpr MInt &operator+=(MInt rhs) &
    {
        x = norm(x + rhs.x);
        return *this;
    }
    constexpr MInt &operator-=(MInt rhs) &
    {
        x = norm(x - rhs.x);
        return *this;
    }
    constexpr MInt &operator/=(MInt rhs) &
    {
        return *this *= rhs.inv();
    }
    friend constexpr MInt operator*(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res *= rhs;
        return res;
    }
    friend constexpr MInt operator+(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res += rhs;
        return res;
    }
    friend constexpr MInt operator-(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res -= rhs;
        return res;
    }
    friend constexpr MInt operator/(MInt lhs, MInt rhs)
    {
        MInt res = lhs;
        res /= rhs;
        return res;
    }
    friend constexpr std::istream &operator>>(std::istream &is, MInt &a)
    {
        i64 v;
        is >> v;
        a = MInt(v);
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a)
    {
        return os << a.val();
    }
    friend constexpr bool operator==(MInt lhs, MInt rhs)
    {
        return lhs.val() == rhs.val();
    }
    friend constexpr bool operator!=(MInt lhs, MInt rhs)
    {
        return lhs.val() != rhs.val();
    }
};

template <>
int MInt<0>::Mod = 1000000007;

template <int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 1000000007;
using Z = MInt<P>;

// 根据输入内容动态修改 MOD 的方法：Z::setMod(p);
template <typename T>
struct Matrix
{
    int n = 4;
    vector<vector<T>> a;
    Matrix() { init(); }
    void init()
    {
        a.resize(n + 1, std::vector<T>(n + 1, 0));
    }
    void i1()
    {
        a.assign(n + 1, std::vector<T>(n + 1, 0));
        for (int i = 1; i <= n; ++i)
            a[i][i] = 1;
    }
    Matrix operator*(const Matrix &y) const
    {
        Matrix z;
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= k; ++i)
                for (int j = i; j <= n; ++j)
                    z.a[i][j] = z.a[i][j] + a[i][k] * y.a[k][j];
        return z;
    }
    Matrix &operator*=(const Matrix &y) &
    {
        Matrix z;
        for (int k = 1; k <= n; ++k)
            for (int i = 1; i <= k; ++i)
                for (int j = i; j <= n; ++j)
                    z.a[i][j] = z.a[i][j] + a[i][k] * y.a[k][j];
        return *this = z;
    }
};
Matrix<Z> lz[N << 2];
struct TR
{
    Z len, sum, sum2, ssum2;
    TR &operator=(const int a) &
    {
        ssum2 = (a * a) % mod;
        sum2 = (a * a) % mod;
        sum = a;
        len = 1;
        return *this;
    }
    TR operator+(const TR y) const
    {
        TR z;
        z.len = len + y.len;
        z.sum = sum + y.sum;
        z.sum2 = sum2 + y.sum2;
        z.ssum2 = ssum2 + y.ssum2;
        return z;
    }
    TR &operator*=(const Matrix<Z> y) &
    {
        ssum2 = len * y.a[1][4] + sum * y.a[2][4] + sum2 * y.a[3][4] + ssum2 * y.a[4][4];
        sum2 = len * y.a[1][3] + sum * y.a[2][3] + sum2 * y.a[3][3];
        sum = len * y.a[1][2] + sum * y.a[2][2];
        return *this;
    }
} tr[N << 2];
int a[N];
#define ls(i) (i << 1)
#define rs(i) (i << 1 | 1)
void push_up(int i) { tr[i] = tr[ls(i)] + tr[rs(i)]; }
void build(int i, int l, int r)
{
    lz[i].i1();
    if (l == r)
    {
        tr[i] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(i), l, mid);
    build(rs(i), mid + 1, r);
    push_up(i);
}
void push_down(int i)
{
    tr[ls(i)] *= lz[i];
    tr[rs(i)] *= lz[i];
    lz[ls(i)] *= lz[i];
    lz[rs(i)] *= lz[i];
    lz[i].i1();
}
void update(int i, int l, int r, int nl, int nr, Matrix<Z> k)
{
    if (l >= nl && r <= nr)
    {
        tr[i] *= k;
        lz[i] *= k;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(i);
    if (nl <= mid)
        update(ls(i), l, mid, nl, nr, k);
    if (nr > mid)
        update(rs(i), mid + 1, r, nl, nr, k);
    push_up(i);
}
Z query(int i, int l, int r, int ql, int qr)
{
    if (l >= ql && r <= qr)
        return tr[i].ssum2;
    Z ans;
    push_down(i);
    int mid = (l + r) >> 1;
    if (ql <= mid)
        ans += query(ls(i), l, mid, ql, qr);
    if (qr > mid)
        ans += query(rs(i), mid + 1, r, ql, qr);
    return ans;
}
Matrix<Z> ak(int x)
{
    Matrix<Z> k;
    k.i1();
    k.a[1][2] = x;
    k.a[1][3] = k.a[1][4] = x * x % mod;
    k.a[2][3] = k.a[2][4] = x * 2 % mod;
    k.a[3][4] = 1;
    return k;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    vector<array<int, 3>> upd(m);
    vector<array<int, 4>> ask(q);
    vector<vector<array<int, 4>>> mp(m + 1);
    for (auto &[l, r, x] : upd)
    {
        cin >> l >> r >> x;
    }
    int id = 0;
    for (auto &[l, r, x, y] : ask)
    {
        cin >> l >> r >> x >> y;
        if (x)
            mp[x - 1].push_back({l, r, id, -1});
        mp[y].push_back({l, r, id, 1});
        id++;
        // mp[x - 1][{l, r}] = 0;
        // mp[y][{l, r}] = 0;
    }
    build(1, 1, n);
    vector<int> akk(q);
    for (int i = 0; i <= m; i++)
    {
        if (i)
        {
            auto [l, r, x] = upd[i - 1];
            update(1, 1, n, l, r, ak(x));
            if (l != 1)
                update(1, 1, n, 1, l - 1, ak(0));
            if (r != n)
                update(1, 1, n, r + 1, n, ak(0));
        }
        for (auto &[l, r, id, ans] : mp[i])
        {
            ans *= query(1, 1, n, l, r).x;
            akk[id] += ans;
        }
    }
    for (auto i : akk)
        cout << i << endl;
    // for (auto [l, r, x, y] : ask)
    // {
    //     Z ans;
    //     ans += mp[y][{l, r}];
    //     if (x)
    //         ans -= mp[x - 1][{l, r}];
    //     cout << ans << endl;
    // }
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 41ms
memory: 84100kb

input:

3 1 1
8 1 6
2 3 2
2 2 0 0

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 31ms
memory: 83316kb

input:

4 3 3
2 3 2 2
1 1 6
1 3 3
1 3 6
2 2 2 3
1 4 1 3
4 4 2 3

output:

180
825
8

result:

ok 3 number(s): "180 825 8"

Test #3:

score: -100
Wrong Answer
time: 45ms
memory: 83708kb

input:

100 107 180
-280960553 266308104 -997644864 856103777 592874377 674379235 -946339772 641750362 642418716 -360811715 -555543246 206614021 358239245 349842656 983198973 807518446 -66612455 -980932737 109826132 -109676067 51226145 452115561 -42729559 -950621304 -87009773 714026474 375317493 693260053 -...

output:

400489222
480617351
531108525
254983761
446689548
764223236
-857770576
307405789
39817281
66225912
247029353
46506707
-470864509
578008236
201809860
674078444
746060191
171471121
-277528534
657196163
861551838
-393448199
-639096051
401221326
-232428092
-330238003
-836240773
141144218
579174939
27655...

result:

wrong answer 7th numbers differ - expected: '142229431', found: '-857770576'
English 繁體中文 简体中文

Server Time: 2024-12-04 22:33:22 | OpenSource Project