ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211237 | #2398. 游戏 | drdilyor | 100 | 1709ms | 50320kb | C++11 | 2.7kb | 2024-08-10 08:43:26 | 2024-08-10 12:33:20 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
int n=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
n=n*10+ch-'0';
ch=getchar();
}
return n*f;
}
const int mod=998244353;
struct mint{
int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a,int b){return a^=b;}
mint operator-(){return 0-*this;}bool operator==(const mint b)const{return x==b.x;}
};
int n,m;
int seg[1000005*4],seg2[1000005*4];
int tag[1000005*4];
void pushdown(int id,int l,int r){
if(!tag[id])return;
int mid=(l+r)/2;
tag[id*2]+=tag[id],tag[id*2+1]+=tag[id];
seg[id*2]+=(mid-l+1)*tag[id],seg[id*2+1]+=tag[id]*(r-mid);
seg2[id*2]+=((l+mid)*(mid-l+1)/2)*tag[id];
seg2[id*2+1]+=((r+mid+1)*(r-mid)/2)*tag[id];
tag[id]=0;
}
void mdf(int id,int l,int r,int ql,int qr,int d){
if(l==ql&&r==qr){
seg[id]+=(r-l+1)*d;
seg2[id]+=d*((l+r)*(r-l+1)/2);
tag[id]+=d;
return;
}
pushdown(id,l,r);
int mid=(l+r)/2;
if(qr<=mid)mdf(id*2,l,mid,ql,qr,d);
else if(ql>mid)mdf(id*2+1,mid+1,r,ql,qr,d);
else mdf(id*2,l,mid,ql,mid,d),mdf(id*2+1,mid+1,r,mid+1,qr,d);
seg[id]=seg[id*2]+seg[id*2+1];
seg2[id]=seg2[id*2]+seg2[id*2+1];
}
int qry(int id,int l,int r,int ql,int qr){
if(l==ql&&r==qr)return seg[id];
pushdown(id,l,r);
int mid=(l+r)/2;
if(qr<=mid)return qry(id*2,l,mid,ql,qr);
if(ql>mid)return qry(id*2+1,mid+1,r,ql,qr);
return qry(id*2,l,mid,ql,mid)+qry(id*2+1,mid+1,r,mid+1,qr);
}
int qry2(int id,int l,int r,int ql,int qr){
if(l==ql&&r==qr)return seg2[id];
pushdown(id,l,r);
int mid=(l+r)/2;
if(qr<=mid)return qry2(id*2,l,mid,ql,qr);
if(ql>mid)return qry2(id*2+1,mid+1,r,ql,qr);
return qry2(id*2,l,mid,ql,mid)+qry2(id*2+1,mid+1,r,mid+1,qr);
}
signed main(){
n=read(),m=read();
while(m--){
int ty=read();
if(ty==2){
int l=read(),r=read();
int res=0;
if(l>1)res+=qry(1,1,n,1,l-1)*(r-l+1);
if(l<=r)res+=qry(1,1,n,l,r)*(r+1);
res-=qry2(1,1,n,l,r);
printf("%lld\n",res);
}
else{
int s=read(),l=read(),r=read();
mdf(1,1,n,l,r,s);
if(r<n)mdf(1,1,n,r+1,r+1,-(r-l+1)*s);
}
}
return 0;
}
Details
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 5ms
memory: 1932kb
input:
10000 10000 2 7160 9968 1 -473 6964 8476 1 -153 5216 7023 2 6352 6868 1 -323 2338 2855 1 415 8414 88...
output:
0 -110345895 -118168581 -43417983 -4860827434 -604843653 -2613457133 -534205626 -89290630 484290874 ...
result:
ok 5015 lines
Test #2:
score: 10
Accepted
time: 6ms
memory: 1936kb
input:
10000 10000 1 326 2291 8264 2 2344 3512 1 146 4506 4804 1 342 1373 4495 1 -267 929 3525 1 444 3384 8...
output:
243137972 7529843014 0 11315350608 10741570136 -23729193 8497340876 11134190564 4752384896 166579811...
result:
ok 5048 lines
Test #3:
score: 10
Accepted
time: 43ms
memory: 48996kb
input:
666666 10000 1 92 555251 586462 1 393 28541 523118 1 448 17256 369367 1 -28 89257 596132 1 -338 3136...
output:
-414130189712976 77743328869266 -733317938115289 -16114105741314 -728855592871891 -618655286944621 -...
result:
ok 1111 lines
Test #4:
score: 10
Accepted
time: 160ms
memory: 50320kb
input:
666666 50000 1 -249 309981 333889 1 477 309512 463171 1 0 71655 592642 1 45 191249 527454 1 55 38872...
output:
120968444808072 -37038538159888 -1101768280866595 -1522590947086835 12009109183517 -363676922444525 ...
result:
ok 5555 lines
Test #5:
score: 10
Accepted
time: 309ms
memory: 50316kb
input:
666666 100000 1 -183 598736 630118 1 -337 605875 639236 1 -62 265069 340682 1 -96 370300 571646 1 -1...
output:
-250805903081209 -53573550596528 -209778044605386 707244607925095 687363641118024 -353194926792326 1...
result:
ok 11111 lines
Test #6:
score: 10
Accepted
time: 299ms
memory: 50316kb
input:
666666 100000 2 121929 379928 2 34550 66844 1 96 338911 637923 2 161666 370147 1 -282 313713 463127 ...
output:
0 0 46837507488 -2144565871356 12891851830 8888329560532 3600670974792 5838384797676 5198143259786 3...
result:
ok 49753 lines
Test #7:
score: 10
Accepted
time: 192ms
memory: 50316kb
input:
750000 100000 1 -318 454211 721481 2 239247 294171 2 52513 339575 2 424462 638364 2 683282 740790 1 ...
output:
0 0 -5392147899330 -3014688113400 -1060371486324 -3974117952270 273653038350 -222431173482 371388923...
result:
ok 49624 lines
Test #8:
score: 10
Accepted
time: 238ms
memory: 50316kb
input:
1000000 100000 1 -108 318728 708230 1 -242 8738 411540 1 -119 458000 972357 2 368015 850304 1 -182 1...
output:
-21232196185685 -20910538239000 -3733012342070 -66375750961180 -16926598739637 -12520509636427 -5091...
result:
ok 49764 lines
Test #9:
score: 10
Accepted
time: 230ms
memory: 50316kb
input:
1000000 100000 2 347033 984386 2 277881 323793 1 431 735974 973576 2 782909 863840 1 -22 379088 6406...
output:
0 0 3048712203338 -275350879342 2861261347158 10963743541855 980271778300 5329951205134 712899593630...
result:
ok 49769 lines
Test #10:
score: 10
Accepted
time: 227ms
memory: 50320kb
input:
1000000 100000 1 -238 406279 814973 1 -425 637451 721356 1 237 340114 658854 2 279214 591961 2 17862...
output:
3413253435344 4249749642085 3270374154195 -7408047958251 0 23029818546288 18074770628646 28102134374...
result:
ok 49741 lines
Extra Test:
score: 0
Extra Test Passed