QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#698574 | #8139. Ayano and sequences | Monkey_Lee | WA | 0ms | 20372kb | C++23 | 2.6kb | 2024-11-01 20:34:30 | 2024-11-01 20:34:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=510000;
const int maxt=2001000;
struct qry
{
int l,r,val,id;
};
struct add
{
int l,r,x;
};
vector<qry> Q[maxn];
vector<add> A[maxn];
int n,q,a[maxn];
int t[maxn],l[maxn],r[maxn],w[maxn],val[maxn];
unsigned long long ans[maxn],sum1[maxt],tag1[maxt],sum2[maxt],tag2[maxt];
set<int> S;
void add1(int p,int l,int r,int x,int y,unsigned long long v)
{
if(l>=x&&r<=y)
{
tag1[p]+=v;
sum1[p]+=(r-l+1)*v;
return ;
}
int mid=(l+r)/2;
if(x<=mid)
add1(p+p,l,mid,x,y,v);
if(y>mid)
add1(p+p+1,mid+1,r,x,y,v);
sum1[p]=sum1[p+p]+sum1[p+p+1];
}
unsigned long long ask1(int p,int l,int r,int x,int y,unsigned long long cnt=0)
{
if(l>=x&&r<=y)
return sum1[p]+cnt*(r-l+1);
int mid=(l+r)/2;
long long ans=0;
cnt+=tag1[p];
if(x<=mid)
ans+=ask1(p+p,l,mid,x,y,cnt);
if(y>mid)
ans+=ask1(p+p+1,mid+1,r,x,y,cnt);
return ans;
}
void add2(int p,int l,int r,int x,int y,unsigned long long v)
{
if(l>=x&&r<=y)
{
tag2[p]+=v;
sum2[p]+=(r-l+1)*v;
return ;
}
int mid=(l+r)/2;
if(x<=mid)
add2(p+p,l,mid,x,y,v);
if(y>mid)
add2(p+p+1,mid+1,r,x,y,v);
sum2[p]=sum2[p+p]+sum2[p+p+1];
}
unsigned long long ask2(int p,int l,int r,int x,int y,unsigned long long cnt=0)
{
if(l>=x&&r<=y)
return sum2[p]+cnt*(r-l+1);
int mid=(l+r)/2;
long long ans=0;
cnt+=tag2[p];
if(x<=mid)
ans+=ask2(p+p,l,mid,x,y,cnt);
if(y>mid)
ans+=ask2(p+p+1,mid+1,r,x,y,cnt);
return ans;
}
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=q;i++)
scanf("%d%d%d%d",&t[i],&l[i],&r[i],&w[i]);
for(int i=0;i<=n;i++)
S.insert(i);
for(int i=1;i<=n;i++)
Q[0].emplace_back(i,i,-1,i),val[i]=i;
for(int i=1;i<=q;i++)
{
if(t[i]==1)
{
l[i]--;
auto L=*(--S.upper_bound(l[i])),R=*S.lower_bound(r[i]);
int las=L,sec=*S.upper_bound(L);
while(las!=R)
{
int p=*S.upper_bound(las);
if(p!=R)
S.erase(p);
Q[i-1].emplace_back(las+1,p,1,val[p]);
las=p;
}
if(L!=l[i])
{
Q[i-1].emplace_back(L+1,l[i],-1,val[sec]);
val[l[i]]=val[sec];
S.insert(l[i]);
}
if(R!=r[i])
{
Q[i-1].emplace_back(r[i]+1,R,-1,val[R]);
S.insert(r[i]);
}
val[r[i]]=w[i];
Q[i-1].emplace_back(l[i]+1,r[i],-1,w[i]);
}
else
A[i].emplace_back(l[i],r[i],w[i]);
}
int las=-1;
for(auto t:S)
{
if(las!=-1)
Q[q].emplace_back(las+1,t,1,val[t]);
las=t;
}
for(int i=0;i<=q;i++)
{
for(auto [l,r,w]:A[i])
add1(1,1,n,l,r,w),add2(1,1,n,l,r,1ull*w*i);
for(auto [l,r,val,id]:Q[i])
ans[id]+=val*(1ull*ask1(1,1,n,l,r)*(i+1)-ask2(1,1,n,l,r));
}
for(int i=1;i<=n;i++)
printf("%lld ",ans[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 20372kb
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: -100
Wrong Answer
time: 0ms
memory: 20200kb
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 1795206697 1618631531 1618631531 47709359896 2215968376 2215968376 1712336204 5993176714
result:
wrong answer 1st lines differ - expected: '0 1795206697 5993176714 221596...98 46271691633 0 5629806604 0 0', found: '0 1795206697 1795206697 161863...15968376 1712336204 5993176714 '