QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115853 | #4118. 音质检测 | Hadtsti | 15 | 282ms | 14216kb | C++14 | 3.7kb | 2023-06-27 15:35:13 | 2023-06-27 15:35:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
int n,l,r,nq;
long long a,b,v[300010];
void rd(int &x)
{
x=0;
char c=getchar();
for(;c>'9'||c<'0';c=getchar());
for(;c<='9'&&c>='0';c=getchar())
x=(x<<3)+(x<<1)+c-'0';
}
void rd(long long &x)
{
x=0ll;
char c=getchar();
for(;c>'9'||c<'0';c=getchar());
for(;c<='9'&&c>='0';c=getchar())
x=(x<<3ll)+(x<<1ll)+c-'0';
}
void pt(long long x)
{
if(x>=10ll)
pt(x/10ll);
putchar(x%10ll+'0');
}
struct matrix
{
int n,m;
long long a[4][4];
void init(int k)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(i!=j)
a[i][j]=0;
else
a[i][j]=k;
}
friend matrix operator*(matrix a,matrix b)
{
matrix c;
c.n=a.n,c.m=b.m;
c.init(0);
for(int i=1;i<=c.n;i++)
for(int k=1;k<=b.n;k++)
for(int j=1;j<=c.m;j++)
(c.a[i][j]+=a.a[i][k]*b.a[k][j]%mod)%=mod;
return c;
}
friend matrix operator+(matrix a,matrix b)
{
matrix c;
c.n=a.n,c.m=a.m;
c.init(0);
for(int i=1;i<=c.n;i++)
for(int j=1;j<=c.m;j++)
c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
return c;
}
friend matrix operator!(matrix a)
{
matrix c;
c.n=a.m,c.m=a.n;
for(int i=1;i<=c.n;i++)
for(int j=1;j<=c.m;j++)
c.a[i][j]=a.a[j][i];
return c;
}
friend matrix operator ^(matrix a,long long b)
{
matrix c;
c.n=c.m=a.n,c.init(1);
for(;b;b>>=1ll)
{
if(b&1ll)
c=c*a;
a=a*a;
}
return c;
}
}ept,pl,mi,tpl,tmi,f,tf,dm;
long long ni(long long x)
{
long long res=1ll,b=mod-2;
for(;b;b>>=1ll)
{
if(b&1ll)
res=res*x%mod;
x=x*x%mod;
}
return res;
}
void make(matrix &a)
{
a.n=3,a.m=3;
}
string op;
struct nd
{
int l,r;
matrix s,tl,tr;
}T[1200010];
void pushup(int x)
{
T[x].s=T[x<<1].s+T[x<<1|1].s;
}
inline void pushdown(int x)
{
T[x<<1].s=T[x].tl*T[x<<1].s*T[x].tr;
T[x<<1|1].s=T[x].tl*T[x<<1|1].s*T[x].tr;
T[x<<1].tl=T[x].tl*T[x<<1].tl;
T[x<<1|1].tl=T[x].tl*T[x<<1|1].tl;
T[x<<1].tr=T[x<<1].tr*T[x].tr;
T[x<<1|1].tr=T[x<<1|1].tr*T[x].tr;
T[x].tl.init(1),T[x].tr.init(1);
}
void build(int p,int l,int r)
{
T[p].l=l,T[p].r=r;
make(T[p].tl),make(T[p].tr);
T[p].tl.init(1),T[p].tr.init(1);
if(l==r)
{
T[p].s=(pl^(v[l-1]-1))*f;
T[p].s=T[p].s*tf*(tpl^(v[l+1]-3));
return;
}
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void change(int p,int L,int R,matrix lv,matrix rv)
{
int l=T[p].l,r=T[p].r;
if(l>R||r<L)
return;
if(L<=l&&r<=R)
{
T[p].s=lv*T[p].s*rv;
T[p].tl=lv*T[p].tl;
T[p].tr=T[p].tr*rv;
return;
}
pushdown(p);
int mid=l+r>>1;
if(L<=mid)
change(p<<1,L,R,lv,rv);
if(R>mid)
change(p<<1|1,L,R,lv,rv);
pushup(p);
}
matrix query(int p,int L,int R)
{
int l=T[p].l,r=T[p].r;
if(L<=l&&r<=R)
return T[p].s;
pushdown(p);
int mid=l+r>>1;
matrix res;
make(res);
res.init(0);
if(R>mid)
res=query(p<<1|1,L,R);
if(L<=mid)
res=res+query(p<<1,L,R);
return res;
}
int main()
{
rd(n),rd(nq),rd(a),rd(b);
for(int i=1;i<=n;i++)
rd(v[i]);
make(pl),make(f);
make(mi),make(ept),make(dm);
ept.init(0),dm.init(1);
pl.a[1][1]=pl.a[2][1]=pl.a[3][3]=1;
pl.a[1][2]=a;
pl.a[1][3]=b;
f.a[1][1]=2;
f.a[2][1]=f.a[3][1]=1;
tpl=!pl;
tf=!f;
if(a)
{
mi.a[1][2]=mi.a[3][3]=1;
mi.a[2][1]=ni(a);
mi.a[2][2]=mod-ni(a);
mi.a[2][3]=mod-b*ni(a)%mod;
}
else
{
mi.a[1][2]=mi.a[2][2]=mi.a[3][3]=1;
mi.a[2][3]=mod-b;
}
tmi=!mi;
build(1,2,n-1);
while(nq--)
{
cin>>op>>l>>r;
if(op=="plus")
change(1,l+1,r+1,pl,dm),change(1,l-1,r-1,dm,tpl);
else if(op=="minus")
change(1,l+1,r+1,mi,dm),change(1,l-1,r-1,dm,tmi);
else if(op=="query")
pt(query(1,l+1,r-1).a[1][1]),putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 153ms
memory: 12688kb
input:
5000 5000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...
output:
30754429 194963785 423087280 568458582 919326931 359004807 861904941 755570340 168436553 373953894 923437580 934015038 585341183 155788638 614511929 116977240 234560163 60030009 118673746 628651237 615800005 308768153 695314874 853373610 496333245 412967503 206869522 856983328 9608271 941717977 6872...
result:
ok 2057 lines
Test #2:
score: 5
Accepted
time: 252ms
memory: 14216kb
input:
7000 7000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...
output:
699552387 116711244 257075385 500055273 63374553 90503904 549081160 162409060 51202676 211756813 786311151 49255389 876981955 909107987 835214464 143761702 376141766 578393672 364811199 708437438 15462795 403930144 938168704 251680630 167431629 229107418 203033028 153135539 315236576 341269317 62012...
result:
ok 2771 lines
Test #3:
score: 5
Accepted
time: 282ms
memory: 14040kb
input:
8000 8000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190059...
output:
364216242 33589407 13036783 289758383 751963601 304836331 441157937 116807134 470264951 877456989 408962375 260881052 254546045 856816319 528760090 771670173 484913701 886579595 323359736 147054683 255504035 717899331 456158394 361180578 634404961 957834998 891216116 346677655 831971764 650152480 52...
result:
ok 3197 lines
Test #4:
score: 0
Time Limit Exceeded
input:
200000 8000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 1900...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
250000 9000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 1900...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
300000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #7:
score: 0
Time Limit Exceeded
input:
200000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #8:
score: 0
Time Limit Exceeded
input:
230000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
250000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
270000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
290000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
300000 10000 0 1 1628547774 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 14287461...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
250000 10000 0 628547775 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 ...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
300000 10000 0 628547775 1786481516 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 ...
output:
result:
Test #15:
score: 0
Time Limit Exceeded
input:
250000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #16:
score: 0
Time Limit Exceeded
input:
260000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #17:
score: 0
Time Limit Exceeded
input:
270000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
280000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
290000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
300000 10000 628547775 786481517 1370685778 1206951921 1334801641 1305387686 1129943687 1053458585 1938363405 1798117303 1383647667 1894428616 1593179275 1542170371 1735380745 1428015135 1652829643 1589283829 1986299923 1221178634 1303777454 1841907098 1919119680 1004204285 1978103602 1428746109 190...