QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#250634#6435. Paimon Segment Treehhoppitree#WA 5ms22000kbC++143.9kb2023-11-13 14:35:382023-11-13 14:35:39

Judging History

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

  • [2023-11-13 14:35:39]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:22000kb
  • [2023-11-13 14:35:38]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 50005, P = 1e9 + 7;

int a[N], _l[N], _r[N], _v[N], A[N];
vector< pair<int, pair<int, int> > > qr[N];

struct mat
{
    int o[4][4];

    mat(int a = 1, int b = 0, int c = 0, int d = 0, int e = 0, int f = 1, int g = 0, int h = 0, int i = 0, int j = 0, int k = 1, int l = 0, int m = 0, int n = 0, int O = 0, int p = 1)
    {
        o[0][0] = a, o[0][1] = b, o[0][2] = c, o[0][3] = d;
        o[1][0] = e, o[1][1] = f, o[1][2] = g, o[1][3] = h;
        o[2][0] = i, o[2][1] = j, o[2][2] = k, o[2][3] = l;
        o[3][0] = m, o[3][1] = n, o[3][2] = O, o[3][3] = p;
        return;
    }

    mat operator + (mat y)
    {
        mat res;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                ((res.o[i][j] = o[i][j] + y.o[i][j]) >= P) && (res.o[i][j] -= P);
            }
        }
        return res;
    }

    mat operator * (mat y)
    {
        mat res(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
        for (int i = 0; i < 4; ++i) {
            for (int k = 0; k < 4; ++k) {
                for (int j = 0; j < 4; ++j) {
                    res.o[i][j] = (res.o[i][j] + 1ll * o[i][k] * y.o[k][j]) % P;
                }
            }
        }
        return res;
    }
} p[1 << 17], q[1 << 17];

void build(int k, int l, int r)
{
    if (l == r) {
        return;
    }
    int mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    p[k] = p[k << 1] + p[k << 1 | 1];
    return;
}

void modify(int k, int l, int r, int x, int y, mat o)
{
    if (l > y || r < x) {
        return;
    }
    if (l >= x && r <= y) {
        p[k] = p[k] * o;
        q[k] = q[k] * o;
        return;
    }
    p[k << 1] = p[k << 1] * q[k];
    q[k << 1] = q[k << 1] * q[k];
    p[k << 1 | 1] = p[k << 1 | 1] * q[k];
    q[k << 1 | 1] = q[k << 1 | 1] * q[k];
    q[k] = mat();
    int mid = (l + r) >> 1;
    modify(k << 1, l, mid, x, y, o);
    modify(k << 1 | 1, mid + 1, r, x, y, o);
    p[k] = p[k << 1] + p[k << 1 | 1];
    return;
}

mat query(int k, int l, int r, int x, int y)
{
    if (l > y || r < x) {
        return mat(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
    }
    if (l >= x && r <= y) {
        return p[k];
    }
    p[k << 1] = p[k << 1] * q[k];
    q[k << 1] = q[k << 1] * q[k];
    p[k << 1 | 1] = p[k << 1 | 1] * q[k];
    q[k << 1 | 1] = q[k << 1 | 1] * q[k];
    q[k] = mat();
    int mid = (l + r) >> 1;
    return query(k << 1, l, mid, x, y) + query(k << 1 | 1, mid + 1, r, x, y);
}

signed main()
{
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &_l[i], &_r[i], &_v[i]);
    }
    for (int i = 1; i <= q; ++i) {
        int l, r, x, y;
        scanf("%d%d%d%d", &l, &r, &x, &y);
        if (x) {
            qr[x - 1].push_back(make_pair(-i, make_pair(l, r)));
        }
        qr[y].push_back(make_pair(i, make_pair(l, r)));
    }
    build(1, 1, n);
    for (int i = 0; i <= m; ++i) {
        if (i) {
            int v = _v[i];
            modify(1, 1, n, _l[i], _r[i], mat(1, v, 1ll * v * v % P, 0, 0, 1, (v + v) % P, 0, 0, 0, 1, 0, 0, 0, 0, 1));
        } else {
            for (int j = 1; j <= n; ++j) {
                int v = a[j];
                modify(1, 1, n, j, j, mat(1, v, 1ll * v * v % P, 0, 0, 1, (v + v) % P, 0, 0, 0, 1, 0, 0, 0, 0, 1));
            }
        }
        modify(1, 1, n, 1, n, mat(1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1));
        for (auto t : qr[i]) {
            A[abs(t.first)] += (t.first > 0 ? 1 : -1) * (query(1, 1, n, t.second.first, t.second.second).o[0][3]);
        }
    }
    for (int i = 1; i <= q; ++i) {
        printf("%d\n", (A[i] % P + P) % P);
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 21196kb

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: 2ms
memory: 22000kb

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: 5ms
memory: 21192kb

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
236141257
549951029
446689548
14056028
142229431
602373057
219686346
66225912
247029353
353738418
529135498
586096834
201809860
674078444
746060191
171471121
902340538
657196163
156519099
606551808
360903956
632566225
767571915
922826851
163759234
141144218
579174939
276557168
34...

result:

wrong answer 3rd numbers differ - expected: '531108525', found: '236141257'