QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#680656 | #6435. Paimon Segment Tree | Left0807 | WA | 35ms | 82036kb | C++20 | 4.2kb | 2024-10-26 22:00:50 | 2024-10-26 22:00:51 |
Judging History
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'