QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#216453#6435. Paimon Segment TreevegWA 1ms6216kbC++143.5kb2023-10-15 18:34:512023-10-15 18:34:51

Judging History

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

  • [2023-10-15 18:34:51]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:6216kb
  • [2023-10-15 18:34:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn=5e4+10;
const int mod=1e9+7;

struct Mdf
{
	int l,r,x;	
}b[maxn];
int a[maxn];
struct Req
{
	int l,r,opt,id;	
};
vector<Req> req[maxn];
int ans[maxn];
struct Node
{
	int tim,sum,sumk,sum2,lenk,sum3,add,add2;
}t[maxn<<2];

void push_up(int x,int tim)
{
	t[x].sum=(t[x<<1].sum+t[x<<1|1].sum)%mod;
	t[x].sum2=(t[x<<1].sum2+t[x<<1|1].sum2)%mod;
	t[x].sum3=(1ll*(tim-t[x<<1].tim)*t[x<<1].sum2+t[x<<1].sum3+1ll*(tim-t[x<<1|1].tim)*t[x<<1|1].sum2+t[x<<1|1].sum3)%mod;
	t[x].tim=tim;
}

void build(int x,int l,int r)
{
	if(l==r) return t[x].sum=(a[l]+mod)%mod,t[x].sum2=t[x].sum3=1ll*a[l]*a[l]%mod,void();
	int mid=l+r>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	push_up(x,0);
}

void push_down(int x,int l,int r)
{
	t[x<<1].sumk=(t[x<<1].sumk+t[x].sumk)%mod;
	t[x<<1|1].sumk=(t[x<<1|1].sumk+t[x].sumk)%mod;
	t[x<<1].lenk=(t[x<<1].lenk+t[x].lenk)%mod;
	t[x<<1|1].lenk=(t[x<<1|1].lenk+t[x].lenk)%mod;
	t[x<<1].add=(t[x<<1].add+t[x].add)%mod;
	t[x<<1|1].add=(t[x<<1|1].add+t[x].add)%mod;
	t[x<<1].add2=(t[x<<1].add2+t[x].add2)%mod;
	t[x<<1|1].add2=(t[x<<1|1].add2+t[x].add2)%mod;
	int mid=l+r>>1;
	t[x<<1].sum3=(t[x<<1].sum3+1ll*t[x].sumk*t[x<<1].sum+1ll*t[x].lenk*(mid-l+1))%mod;
	t[x<<1|1].sum3=(t[x<<1|1].sum3+1ll*t[x].sumk*t[x<<1|1].sum+1ll*t[x].lenk*(r-mid))%mod;
	t[x<<1].sum2=(t[x<<1].sum2+2ll*t[x].add*t[x<<1].sum+1ll*t[x].add2*(mid-l+1))%mod;
	t[x<<1|1].sum2=(t[x<<1|1].sum2+2ll*t[x].add*t[x<<1|1].sum+1ll*t[x].add2*(r-mid))%mod;
	t[x<<1].sum=(t[x<<1].sum+1ll*t[x].add*(mid-l+1))%mod;
	t[x<<1|1].sum=(t[x<<1|1].sum+1ll*t[x].add*(r-mid))%mod;
	t[x<<1].tim=t[x<<1|1].tim=t[x].tim;
	t[x].lenk=t[x].sumk=t[x].add=t[x].add2=0;
}

void modify(int x,int l,int r,int left,int right,int val,int tim)
{
	if(l>=left&&r<=right)
	{
		int len=r-l+1;
		t[x].sumk=(t[x].sumk+2ll*(tim-t[x].tim)*t[x].add+val*2)%mod;
		t[x].lenk=(t[x].lenk+1ll*(tim-t[x].tim)*t[x].add2+1ll*val*val)%mod;
		t[x].add=(t[x].add+val)%mod;
		t[x].add2=(t[x].add2+1ll*val*val)%mod;
		t[x].sum3=(t[x].sum3+1ll*t[x].sum2*(tim-t[x].tim)+2ll*val*t[x].sum+1ll*val*val%mod*len)%mod;
		t[x].sum2=(t[x].sum2+2ll*val*t[x].sum+1ll*val*val%mod*len)%mod;
		t[x].sum=(t[x].sum+1ll*val*len)%mod;
		t[x].tim=tim;
		printf("[%d %d %d]\n",l,r,t[x].sum3);
		return;
	}
	int mid=l+r>>1;
	push_down(x,l,r);
	if(left<=mid) modify(x<<1,l,mid,left,right,val,tim);
	if(right>mid) modify(x<<1|1,mid+1,r,left,right,val,tim);
	push_up(x,tim);
}

int query(int x,int l,int r,int left,int right,int tim)
{
	if(l>=left&&r<=right) return (1ll*(tim-t[x].tim)*t[x].sum2+t[x].sum3)%mod;
	int mid=l+r>>1,ans=0;
	push_down(x,l,r);
	if(left<=mid) ans+=query(x<<1,l,mid,left,right,tim);
	if(right>mid) ans+=query(x<<1|1,mid+1,r,left,right,tim);
	return ans%mod;
}

int main()
{
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&b[i].l,&b[i].r,&b[i].x);
	for(int i=1;i<=q;i++)
	{
		int l,r,x,y;
		scanf("%d%d%d%d",&l,&r,&x,&y);
		if(x) req[x-1].push_back((Req){l,r,mod-1,i});
		req[y].push_back((Req){l,r,1,i});
	}
	for(auto v:req[0])
		ans[v.id]=(ans[v.id]+1ll*v.opt*query(1,1,n,v.l,v.r,0))%mod;
	for(int i=1;i<=m;i++)
	{
		modify(1,1,n,b[i].l,b[i].r,(b[i].x+mod)%mod,i);
		if(b[i].l>1) modify(1,1,n,1,b[i].l-1,0,i);
		if(b[i].r<n) modify(1,1,n,b[i].r+1,n,0,i);
		printf("{%d}\n",t[1].sum3);
		for(auto v:req[i])
			ans[v.id]=(ans[v.id]+1ll*v.opt*query(1,1,n,v.l,v.r,i))%mod;
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 6216kb

input:

3 1 1
8 1 6
2 3 2
2 2 0 0

output:

[2 2 10]
[3 3 100]
[1 1 64]
{174}
1

result:

wrong output format Expected integer, but "[2" found