QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#698574#8139. Ayano and sequencesMonkey_LeeWA 0ms20372kbC++232.6kb2024-11-01 20:34:302024-11-01 20:34:30

Judging History

你现在查看的是最新测评结果

  • [2024-11-01 20:34:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:20372kb
  • [2024-11-01 20:34:30]
  • 提交

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 '