QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#223225#6435. Paimon Segment TreeOkuchiriWA 4ms17432kbC++204.8kb2023-10-21 22:42:132023-10-21 22:42:13

Judging History

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

  • [2023-10-21 22:42:13]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:17432kb
  • [2023-10-21 22:42:13]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0)
#define mod 1000000007
using namespace std;
struct tr
{
    ll x[5];
}a[200040];
struct ma
{
    ll v[5][5];
}laz[200040];
struct tri
{
    ll l,r,p;
};
tr operator * (tr p,ma q)
{
    tr res;
    memset(res.x,0,sizeof(res.x));
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=4;j++)
        {
            res.x[i]=(res.x[i]+p.x[j]*q.v[j][i]%mod)%mod;
        }
    }
    return res;
}
ma operator * (ma p ,ma q)
{
    ma res;
    memset(res.v,0,sizeof(res.v));
    for(int i=1;i<=4;i++)
    for(int j=1;j<=4;j++)
    for(int k=1;k<=4;k++)
    res.v[i][j]=(res.v[i][j]+p.v[i][k]*q.v[k][j]%mod)%mod;
    return res;
}
bool operator == (ma p,ma q)
{
    for(int i=1;i<=4;i++)
    for(int j=1;j<=4;j++)if(p.v[i][j]!=q.v[i][j])return 0;
    return 1;
} 
ll n,m,q,ini[100010],op[100010][4];
ll qu2[100010][5],ans[100010],sq[100010];
vector<tri> qu[100010];
ma dw;
void reset(int t)
{
    memset(laz[t].v,0,sizeof(laz[t].v));
    for(int i=1;i<=4;i++)laz[t].v[i][i]=1;
}
void build(int now,int l,int r)
{
    if(l==r)
    {
        a[now].x[1]=1;
        a[now].x[2]=ini[l]%mod;
        a[now].x[3]=ini[l]*ini[l]%mod;
        a[now].x[4]=ini[l]*ini[l]%mod;
        reset(now);
        return;
    }
    int mid=(l+r)/2;
    reset(now);
    build(now*2,l,mid);
    build(now*2+1,mid+1,r);
    a[now].x[1]=(a[now*2].x[1]+a[now*2+1].x[1])%mod;
    a[now].x[2]=(a[now*2].x[2]+a[now*2+1].x[2])%mod;
    a[now].x[3]=(a[now*2].x[3]+a[now*2+1].x[3])%mod;
    a[now].x[4]=(a[now*2].x[4]+a[now*2+1].x[4])%mod;
    //cout<<a[now].x[4]<<'\n';
}
void pushdown(int now,int l,int r)
{
    if(laz[now]==dw)return;
    a[now*2]=a[now*2]*laz[now];
    a[now*2+1]=a[now*2+1]*laz[now];
    laz[now*2]=laz[now*2]*laz[now];
    laz[now*2+1]=laz[now*2+1]*laz[now];
    reset(now);
}
void change(int now,int l,int r,int l1,int r1,ma k)
{
    if(l1>r1)return;
    if(l>=l1&&r1>=r)
    {
        a[now]=a[now]*k;
        laz[now]=laz[now]*k;
        return;
    }
    int mid=(l+r)/2;
    pushdown(now,l,r);
    if(l1<=mid)change(now*2,l,mid,l1,r1,k);
    if(r1>=mid+1)change(now*2+1,mid+1,r,l1,r1,k);
    a[now].x[1]=(a[now*2].x[1]+a[now*2+1].x[1])%mod;
    a[now].x[2]=(a[now*2].x[2]+a[now*2+1].x[2])%mod;
    a[now].x[3]=(a[now*2].x[3]+a[now*2+1].x[3])%mod;
    a[now].x[4]=(a[now*2].x[4]+a[now*2+1].x[4])%mod;
}
ll query(int now,int l,int r,int l1,int r1)
{
    if(l1>r1)return 0;
    if(l1<=l&&r1>=r)
    {
        return a[now].x[4]%mod;
    }
    pushdown(now,l,r);
    int mid=(l+r)/2;
    ll res=0;
    if(l1<=mid)res=(res+query(now*2,l,mid,l1,r1))%mod;
    if(r1>=mid+1)res=(res+query(now*2+1,mid+1,r,l1,r1))%mod;
    a[now].x[1]=(a[now*2].x[1]+a[now*2+1].x[1])%mod;
    a[now].x[2]=(a[now*2].x[2]+a[now*2+1].x[2])%mod;
    a[now].x[3]=(a[now*2].x[3]+a[now*2+1].x[3])%mod;
    a[now].x[4]=(a[now*2].x[4]+a[now*2+1].x[4])%mod;
    return res%mod;
}
signed main()
{
    IOS;
    cin>>n>>m>>q;
    memset(dw.v,0,sizeof(dw.v));for(int i=1;i<=4;i++)dw.v[i][i]=1;
    for(int i=1;i<=n;i++)cin>>ini[i];
    for(int i=1;i<=m;i++)
    {
        cin>>op[i][1]>>op[i][2]>>op[i][3];
    }
    for(int i=1;i<=q;i++)
    {
        cin>>qu2[i][1]>>qu2[i][2]>>qu2[i][3]>>qu2[i][4];
        tri tem;
        if(qu2[i][3]>0)
        {
            tem.l=qu2[i][1];tem.r=qu2[i][2];tem.p=i;
            sq[qu2[i][3]-1]++;
            qu[qu2[i][3]-1].push_back(tem);
        }
        else
        {
            ans[i]=0;
        }
        tem.l=qu2[i][1];tem.r=qu2[i][2];tem.p=i+q;
        sq[qu2[i][4]]++;
        qu[qu2[i][4]].push_back(tem);
    }
    build(1,1,n);
    for(int i=0;i<sq[0];i++)
    {
        ll l=qu[0][i].l,r=qu[0][i].r,p=qu[0][i].p;
        ans[p]=query(1,1,n,l,r);
    }
    for(int i=1;i<=m;i++)
    {
        ll l=op[i][1],r=op[i][2],k=op[i][3];
        ma w;
        memset(w.v,0,sizeof(w.v));
        w.v[1][1]=1;
        w.v[1][2]=k%mod;
        w.v[1][3]=k*k%mod;
        w.v[1][4]=k*k%mod;
        w.v[2][2]=1;
        w.v[2][3]=2ll*k%mod;
        w.v[2][4]=2ll*k%mod;
        w.v[3][3]=1;
        w.v[3][4]=1;
        w.v[4][4]=1;
        change(1,1,n,l,r,w);
        w.v[1][1]=1;
        w.v[1][2]=0;
        w.v[1][3]=0;
        w.v[1][4]=0;
        w.v[2][2]=1;
        w.v[2][3]=0;
        w.v[2][4]=0;
        w.v[3][3]=1;
        w.v[3][4]=1;
        w.v[4][4]=1;
        change(1,1,n,1,l-1,w);
        change(1,1,n,r+1,n,w);
        for(int j=0;j<sq[i];j++)
        {
            ans[qu[i][j].p]=query(1,1,n,qu[i][j].l,qu[i][j].r);
        }
    }
    for(int i=1;i<=q;i++)
    {
        cout<<(ans[i+q]-ans[i]+1ll*mod)%mod<<'\n';
    }
    //system("pause");
}

详细

Test #1:

score: 100
Accepted
time: 3ms
memory: 17432kb

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: 0ms
memory: 13896kb

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: 4ms
memory: 13956kb

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
529135498
578008236
201809860
674078444
746060191
171471121
722471473
657196163
861551838
606551808
360903956
401221326
767571915
669762004
163759234
141144218
579174939
276557168
518...

result:

wrong answer 77th numbers differ - expected: '826879924', found: '-173120083'