QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#631074 | #8286. Stacks | wangjunrui | WA | 5ms | 10244kb | C++14 | 2.8kb | 2024-10-11 21:51:37 | 2024-10-11 21:51:39 |
Judging History
answer
#include<iostream>
#include <random>
using namespace std;
struct tree
{
int l,r,x,y,size;
long long s,sum;
};
tree a[35000000];
int num=0;
inline int node(int x,int y)
{
num++;
a[num].size=1;
a[num].x=a[num].s=x,a[num].y=y;
a[num].sum=(long long)x*y;
return num;
}
inline void update(int p)
{
a[p].size=a[a[p].l].size+a[a[p].r].size+1;
a[p].s=a[a[p].l].s+a[a[p].r].s+a[p].x;
a[p].sum=a[a[p].l].sum+a[a[p].r].sum
+(long long)a[p].x*a[p].y;
}
mt19937 rnd(114514);
int merge(int x,int y)
{
if(!x||!y)
{
return x|y;
}
int p=++num;
rnd() & 1
?(a[p]=a[x],a[p].r=merge(a[p].r,y))
:(a[p]=a[y],a[p].l=merge(x,a[p].l));
update(p);
return p;
}
int split(int p,long long k)
{
if(!p)
{
return 0;
}
long long t=a[a[p].r].s+a[p].x;
if(k>=t)
{
return split(a[p].l,k-t);
}
if(k<a[a[p].r].s)
{
int P=++num;
a[P]=a[p];
a[P].r=split(a[P].r,k);
update(P);
return P;
}
a[++num]=a[p],a[num].r=0;
a[num].x-=k-a[a[p].r].s;
update(num);
return num;
}
long long query(int p,long long k)
{
if(!p)
{
return 0;
}
if(k<a[a[p].l].s)
{
return query(a[p].l,k);
}
k-=a[a[p].l].s;
if(k<=a[p].x)
{
return a[a[p].l].sum+k*a[p].y;
}
return query(a[p].r,k-a[p].x)
+a[a[p].l].sum+(long long)a[p].x*a[p].y;
}
int n,m,A[400000];
long long d[400000];
inline void del(int p,long long v)
{
if(a[A[p]].s<=v)
{
v-=a[A[p]].s;
A[p]=0,d[p]+=v;
return;
}
A[p]=split(A[p],v);
}
inline void pushdown(int p)
{
if(d[p])
{
del(p<<1,d[p]);
del((p<<1)|1,d[p]);
d[p]=0;
}
if(A[p])
{
A[p<<1]=merge(A[p<<1],A[p]);
A[(p<<1)|1]=merge(A[(p<<1)|1],A[p]);
A[p]=0;
}
}
void add(int l,int r,int ll,int rr,int x,int y,int p)
{
if(r<ll||l>rr)
{
return;
}
if(ll<=l&&r<=rr)
{
A[p]=merge(A[p],node(x,y));
return;
}
pushdown(p);
int mid=l+r>>1;
add(l,mid,ll,rr,x,y,p<<1);
add(mid+1,r,ll,rr,x,y,(p<<1)|1);
}
void del(int l,int r,int ll,int rr,long long x,int p)
{
if(r<ll||l>rr)
{
return;
}
if(ll<=l&&r<=rr)
{
del(p,x);
return;
}
pushdown(p);
int mid=l+r>>1;
del(l,mid,ll,rr,x,p<<1);
del(mid+1,r,ll,rr,x,(p<<1)|1);
}
long long query(int l,int r,int x,long long ll,long long rr,int p)
{
if(l==r)
{
return query(A[p],rr)-query(A[p],ll-1);
}
pushdown(p);
int mid=l+r>>1;
return x<=mid?query(l,mid,x,ll,rr,p<<1)
:query(mid+1,r,x,ll,rr,(p<<1)|1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
while(m--)
{
int op;
cin>>op;
if(op==1)
{
int l,r,x,y;
cin>>l>>r>>x>>y;
add(1,n,l,r,x,y,1);
}
if(op==2)
{
int l,r;
long long x;
cin>>l>>r>>x;
del(1,n,l,r,x,1);
}
if(op==3)
{
int x;
long long l,r;
cin>>x>>l>>r;
cout<<query(1,n,x,l,r,1)<<'\n';
}
}
printf("%d\n", num);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 5ms
memory: 10244kb
input:
4907 4910 2 763 3330 1 3 307 1 1 1 2262 3430 22699 89397 1 1915 4000 51541 67587 2 212 2990 9763 2 1086 2162 1 2 1813 4496 16760 1 51 2796 68005 99390 1 1267 1519 74236 66178 3 1768 23808 54314 2 900 4122 27758 3 3287 17350 28989 2 3277 4024 3633 2 444 4866 1 2 353 4219 1061 1 987 3141 99906 17320 2...
output:
0 3032090730 903396180 471569175 200648623 98486697 647114751 123945 50793012 61782451 0 0 0 762429740 321140700 871619914 536311874 5361094892 0 1792521566 6640518748 2415375780 249435711 225987900 5250788038 1145132507 140071334 0 118545795 3086405469 5646099271 84280112 1232466642 4992966775 7968...
result:
wrong answer Output contains longer sequence [length = 1623], but answer contains 1622 elements