QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#680656#6435. Paimon Segment TreeLeft0807WA 35ms82036kbC++204.2kb2024-10-26 22:00:502024-10-26 22:00:51

Judging History

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

  • [2024-10-26 22:00:51]
  • 评测
  • 测评结果:WA
  • 用时:35ms
  • 内存:82036kb
  • [2024-10-26 22:00:50]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int N = 5e4 + 10;
const int MOD = 1e9 + 7;

struct mat;
struct vec;

struct mat{
    vector<vector<int> > m;

    mat() :
        mat({{0,0,0,0},{0,0,0,0},{0,0,0,0},{0,0,0,0}}) {}

    mat(int k) :
        mat({{1, 1, 2*k, k*k},
             {0, 1, 2*k, k*k},
             {0, 0, 1, k},
             {0, 0, 0, 1}}) {}
    
    mat(vector<vector<int> > m) : m(m) {*this %= MOD;}

    const mat& operator%=(const int k){
        for(auto& x : m) for(auto& y : x) y %= k;
        return *this;
    }

    mat operator*(const mat& o){
        mat res = mat();

        for(int i = 0; i < 4; i++){
            for(int j = 0; j < 4; j++){
                for(int k = 0; k < 4; k++){
                    res.m[i][j] += m[i][k] * o.m[k][j];
                }
            }
        }

        res %= MOD;

        return res;
    }

    void print(){
        for(auto r : m){
            for(auto c : r){
                cout << c << ' ';
            }
            cout << '\n'; 
        }
    }
};

const mat I = mat({{1,0,0,0}, {0,1,0,0}, {0,0,1,0}, {0,0,0,1}});


struct vec{
    vector<int> v;

    vec() : vec({0,0,0,0}) {}
    vec(vector<int> v) : v(v) {*this%=MOD;}

    const vec& operator*=(const mat& o){
        v[0] += v[1] * o.m[0][1] + v[2] * o.m[0][2] + v[3] * o.m[0][3];
        v[1] += v[2] * o.m[1][2] + v[3] * o.m[1][3];
        v[2] += v[3] * o.m[2][3];
        *this %= MOD;
        return *this;
    }

    const vec& operator%=(const int k){
        for(int& x : v) x %= k;
        return *this;
    }

    vec operator+(const vec& o){
        vec res = vec();
        for(int i = 0; i < 4; i++) res.v[i] = v[i] + o.v[i];
        res %= MOD;
        return res;
    }

    void print(){
        for(int x : v) cout << x << ' '; cout << '\n';
    }
};

struct node{
    vec val;
    mat lz;

    node() : val(), lz(I) {}
    node(int x) : val({x*x,x*x,x,1}), lz(I) {}

} tr[4*N];

int a[N];

void build(int v, int l, int r){
    if(l == r){
        tr[v] = node(a[l]);
    } else{
        int mid = (l+r)/2;
        build(2*v, l, mid);
        build(2*v+1, mid+1, r);
        tr[v].val = tr[2*v].val + tr[2*v+1].val; 
    }
}

void push(int v){
    tr[2*v].val *= tr[v].lz;
    tr[2*v+1].val *= tr[v].lz;
    tr[2*v].lz = tr[v].lz * tr[2*v].lz;
    tr[2*v+1].lz = tr[v].lz * tr[2*v+1].lz;
    tr[v].lz = I;
}

void apply(int v){
    tr[v].val *= tr[v].lz;
    push(v);
}

void upd(int v, int l, int r, int ql, int qr, int k){
    if(ql > qr) return;
    if(l > qr || r < ql) return;
    if(ql <= l && r <= qr){
        tr[v].val *= mat(k);
        tr[v].lz = mat(k) * tr[v].lz;
        return;
    }
    int mid = (l+r)/2;
    push(v);
    upd(2*v, l, mid, ql, qr, k);
    upd(2*v+1, mid+1, r, ql, qr, k);
    tr[v].val = tr[2*v].val + tr[2*v+1].val;
}



int qry(int v, int l, int r, int ql, int qr){
    if(l > qr || r < ql) return 0;
    if(ql <= l && r <= qr){
        return tr[v].val.v[0];
    }
    push(v);
    int mid = (l+r)/2;
    return (qry(2*v, l, mid, ql, qr) + qry(2*v+1, mid+1, r, ql, qr))%MOD;
}

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(0); 

    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    // for(int i = 1; i <= n; i++) cout << qry(1, 1, n, i,i) << ' '; cout << '\n';

    vector<array<int,5>> qry_v;
    vector<array<int,3>> upd_v(m);

    for(auto& [l, r, k] : upd_v){
        cin >> l >> r >> k;
    }
    for(int i = 0; i < q; i++){
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        qry_v.push_back({x-1, l, r, -1, i});
        qry_v.push_back({y, l, r, 1, i});
    }
    sort(all(qry_v));
    vector<int> ans(q);
    int pre = 0;
    for(auto [t, l, r, tag, id] : qry_v){
        if(t < 0) continue;
        for(;pre<t; pre++){
            auto [ul, ur, k] = upd_v[pre];
            upd(1, 1, n, ul, ur, k);
            upd(1, 1, n, ur+1, n, 0);
            upd(1, 1, n, 1, ul-1, 0);
        }
        ans[id] += tag * qry(1, 1, n, l, r);
    }
    for(int i = 0; i < q; i++) cout << (ans[i]+MOD)%MOD << '\n';
}


详细

Test #1:

score: 100
Accepted
time: 35ms
memory: 81676kb

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: 81932kb

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: 31ms
memory: 82036kb

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
142229431
307405789
39817281
66225912
247029353
46506707
-470864509
578008236
201809860
674078444
746060191
171471121
722471473
657196163
861551838
606551808
360903956
401221326
-232428092
669762004
163759234
141144218
579174939
276557168
5...

result:

wrong answer 13th numbers differ - expected: '529135498', found: '-470864509'