QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #707152 | #8139. Ayano and sequences | Yaimsea | WA | 1ms | 8028kb | C++20 | 3.0kb | 2024-11-03 14:52:45 | 2024-11-03 14:52:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct segmenttree{
unsigned long long col,sum1,sum2,laspos,bg;
}c[2000010];
unsigned long long n,q,a[500010],ans[500010];
inline void pushdown(unsigned long long i)
{
long long ls=(i<<1),rs=(i<<1|1),t,tnum;
if(!c[i].col)
{
c[ls].sum1+=c[i].sum1,c[rs].sum1+=c[i].sum1;
c[ls].sum2+=c[i].sum2,c[rs].sum2+=c[i].sum2;
c[i].sum1=c[i].sum2=0;
}
else
{
if(!c[ls].col)
{
pushdown(ls);
c[ls]=c[i];
}
else
{
ans[c[ls].col]+=(c[ls].sum2-c[ls].sum1*(q-c[i].laspos+1));
t=c[ls].laspos,tnum=c[ls].sum1;
c[ls]=c[i];
c[ls].laspos=t,c[ls].sum1+=tnum,c[ls].sum2+=(tnum*(q-c[i].bg+1));
}
if(!c[rs].col)
{
pushdown(rs);
c[rs]=c[i];
}
else
{
ans[c[rs].col]+=(c[rs].sum2-c[rs].sum1*(q-c[i].laspos+1));
t=c[rs].laspos,tnum=c[rs].sum1;
c[rs]=c[i];
c[rs].laspos=t,c[rs].sum1+=tnum,c[rs].sum2+=(tnum*(q-c[i].bg+1));
}
c[i].col=c[i].sum1=c[i].sum2=c[i].laspos=0;
}
return;
}
void build(unsigned long long i,unsigned long long l,unsigned long long r)
{
if(l==r)
{
c[i].col=a[l];
return;
}
unsigned long long mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
return;
}
void update1(unsigned long long i,unsigned long long l,unsigned long long r,unsigned long long L,unsigned long long R,unsigned long long col,unsigned long long pos,unsigned long long sum)
{
if(l>=L&&r<=R)
{
//printf("??? %lld %lld %lld %lld\n",i,l,r,sum);
if(!c[i].col)
{
pushdown(i);
c[i].col=col,c[i].sum1=sum,c[i].sum2=sum*(q-pos+1),c[i].laspos=pos,c[i].bg=pos;
}
else
{
ans[c[i].col]+=(c[i].sum2-c[i].sum1*(q-pos+1));
c[i].col=col,c[i].sum1+=sum,c[i].sum2=c[i].sum1*(q-pos+1),c[i].bg=pos;
}
return;
}
pushdown(i);
unsigned long long mid=(l+r)>>1;
if(L<=mid)
update1(i<<1,l,mid,L,R,col,pos,sum);
if(R>=mid+1)
update1(i<<1|1,mid+1,r,L,R,col,pos,sum);
return;
}
void update2(unsigned long long i,unsigned long long l,unsigned long long r,unsigned long long L,unsigned long long R,unsigned long long col,unsigned long long pos)
{
if(l>=L&&r<=R)
{
c[i].sum1+=col,c[i].sum2+=(col*(q-pos+1));
return;
}
pushdown(i);
unsigned long long mid=(l+r)>>1;
if(L<=mid)
update2(i<<1,l,mid,L,R,col,pos);
if(R>=mid+1)
update2(i<<1|1,mid+1,r,L,R,col,pos);
return;
}
void dfs(unsigned long long i,unsigned long long l,unsigned long long r)
{
if(l==r)
{
//printf("??? %lld %lld %lld %lld\n",i,l,c[i].sum2,c[i].sum1);
ans[c[i].col]+=c[i].sum2;
return;
}
pushdown(i);
unsigned long long mid=(l+r)>>1;
dfs(i<<1,l,mid);
dfs(i<<1|1,mid+1,r);
return;
}
int main()
{
unsigned long long i,t,l,r,u;
scanf("%llu %llu",&n,&q);
for(i=1;i<=n;++i)
scanf("%llu",&a[i]);
build(1,1,n);
for(i=1;i<=q;++i)
{
scanf("%llu %llu %llu %llu",&t,&l,&r,&u);
if(t==1)
update1(1,1,n,l,r,u,i,0ll);
else
update2(1,1,n,l,r,u,i);
}
dfs(1,1,n);
for(i=1;i<=n;++i)
printf("%llu ",ans[i]);
return 0;
}
/*
5 3
1 2 3 4 5
2 2 4 1
1 2 3 3
2 3 4 3
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7944kb
input:
5 6 1 2 3 4 5 2 2 4 1 1 2 3 3 2 3 4 3 1 3 5 4 2 1 5 2 1 1 3 2
output:
2 12 12 36 0
result:
ok single line: '2 12 12 36 0 '
Test #2:
score: 0
Accepted
time: 1ms
memory: 8020kb
input:
10 10 9 2 8 8 6 5 4 8 5 3 2 2 6 268792718 2 7 8 125908043 2 2 3 150414369 2 6 10 856168102 2 4 5 274667941 1 1 9 6 2 2 6 646837311 2 6 6 105650419 2 7 9 254786900 2 1 7 73936815
output:
0 1795206697 5993176714 2215968376 4768635998 46271691633 0 5629806604 0 0
result:
ok single line: '0 1795206697 5993176714 221596...8 46271691633 0 5629806604 0 0 '
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 8028kb
input:
100 100 59 96 34 48 8 72 67 90 15 85 7 90 97 47 25 44 69 6 86 32 57 47 21 9 63 10 75 35 61 11 75 100 50 53 15 40 35 86 97 77 27 30 35 91 72 87 56 25 95 70 60 22 47 49 68 61 35 87 16 54 20 91 35 39 64 21 58 44 5 20 61 87 66 74 45 64 9 84 1 26 32 63 53 33 96 47 73 94 45 32 99 14 44 48 1 78 7 10 68 52 ...
output:
11247109332 0 0 0 309880184 347085980 0 5208679581 0 0 395123921992 138666276757 0 309880184 0 309880184 0 1113912923099 0 1470341419 1160461235 0 0 312246591243 1041257940 14067137073 0 74060793330 0 0 489681197597 5634558398 189648022499 125166068190 1470341419 0 0 973698227850 138835083780 105235...
result:
wrong answer 1st lines differ - expected: '274832111654 0 0 0 309880184 3...994 609693254112 307568016399 0', found: '11247109332 0 0 0 309880184 34...60 609693254112 134215883211 0 '