제출 #1326853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326853		boclobanchat	Flooding Wall (BOI24_wall)	C++20	100 / 100	4398 ms	137340 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct value { int x,idx,p; };
bool comp(value a,value b)
{
	if(a.x==b.x)
	{
		if(a.idx==b.idx) return a.p<b.p;
		return a.idx<b.idx;
	}
	return a.x<b.x;
}
const int MAXN=1e6+5;
const long long mod=1e9+7;
value val[MAXN];
pair<int,int> P[MAXN];
pair<long long,long long> A[MAXN],F[2][MAXN],G[2][MAXN];
struct node
{
	long long sum,cnt,lazy1,lazy2,f;
};
node seg[MAXN*4];
node merge(node a,node b)
{
	return {(a.sum+b.sum)%mod,(a.cnt+b.cnt)%mod,1,0,(a.f+b.f)%mod};
}
void build(int l,int r,int pos)
{
	seg[pos]={0,0,1,0,0};
	if(l==r) return ;
	int mid=(l+r)/2;
	build(l,mid,pos*2);
	build(mid+1,r,pos*2+1);
}
void down(int pos)
{
	long long v1=seg[pos].lazy1,v2=seg[pos].lazy2;
	if(v1==1&&v2==0) return ;
	seg[pos*2].sum=(seg[pos*2].sum*v1+seg[pos*2].f*v2)%mod;
	seg[pos*2].cnt=seg[pos*2].cnt*v1%mod;
	seg[pos*2].f=seg[pos*2].f*v1%mod;
	seg[pos*2].lazy2=(seg[pos*2].lazy2*v1+seg[pos*2].lazy1*v2)%mod;
	seg[pos*2].lazy1=seg[pos*2].lazy1*v1%mod;
	seg[pos*2+1].sum=(seg[pos*2+1].sum*v1+seg[pos*2+1].f*v2)%mod;
	seg[pos*2+1].cnt=seg[pos*2+1].cnt*v1%mod;
	seg[pos*2+1].f=seg[pos*2+1].f*v1%mod;
	seg[pos*2+1].lazy2=(seg[pos*2+1].lazy2*v1+seg[pos*2+1].lazy1*v2)%mod;
	seg[pos*2+1].lazy1=seg[pos*2+1].lazy1*v1%mod;
	seg[pos].lazy1=1,seg[pos].lazy2=0;
}
void updset(int l,int r,int i,long long sum,long long cnt,int pos)
{
	if(i<l||r<i) return ;
	if(l==r)
	{
		seg[pos]={sum,cnt,0,0,cnt*val[i].x%mod};
		return ;
	}
	int mid=(l+r)/2;
	down(pos);
	updset(l,mid,i,sum,cnt,pos*2);
	updset(mid+1,r,i,sum,cnt,pos*2+1);
	seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
void update(int l,int r,int u,int v,long long val,int pos)
{
	if(u>v) return ;
	if(u<=l&&r<=v)
	{
		seg[pos].sum=(seg[pos].sum+seg[pos].f)%mod*val%mod;
		seg[pos].cnt=seg[pos].cnt*val%mod;
		seg[pos].f=seg[pos].f*val%mod;
		seg[pos].lazy2=(seg[pos].lazy2+seg[pos].lazy1)%mod*val%mod;
		seg[pos].lazy1=seg[pos].lazy1*val%mod;
		return ;
	}
	int mid=(l+r)/2;
	down(pos);
	if(v<=mid) update(l,mid,u,v,val,pos*2);
	else if(mid+1<=u) update(mid+1,r,u,v,val,pos*2+1);
	else
	{
		update(l,mid,u,v,val,pos*2);
		update(mid+1,r,u,v,val,pos*2+1);
	}
	seg[pos]=merge(seg[pos*2],seg[pos*2+1]);
}
node get(int l,int r,int u,int v,int pos)
{
	if(u<=l&&r<=v) return seg[pos];
	int mid=(l+r)/2;
	down(pos);
	if(v<=mid) return get(l,mid,u,v,pos*2);
	if(mid+1<=u) return get(mid+1,r,u,v,pos*2+1);
	return merge(get(l,mid,u,v,pos*2),get(mid+1,r,u,v,pos*2+1));
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>A[i].first;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i].second;
		if(A[i].first>A[i].second) swap(A[i].first,A[i].second);
		val[++cnt]={A[i].first,i,0},val[++cnt]={A[i].second,i,1};
	}
	sort(val+1,val+cnt+1,comp);
	for(int i=1;i<=cnt;i++) if(val[i].p) P[val[i].idx].second=i;
	else P[val[i].idx].first=i;
	build(0,cnt,1);
	updset(0,cnt,0,0,1,1);
	for(int i=1;i<=n;i++)
	{
		int x=P[i].first,y=P[i].second;
		node f1=get(0,cnt,0,x-1,1);
		node f2=get(0,cnt,0,y-1,1);
		update(0,cnt,0,x-1,0,1);
		update(0,cnt,x+1,y-1,1,1);
		update(0,cnt,y+1,cnt,2,1);
		F[0][i]={(f1.sum+f1.cnt*A[i].first)%mod,f1.cnt};
		F[1][i]={(f2.sum+f2.cnt*A[i].second)%mod,f2.cnt};
		updset(0,cnt,x,F[0][i].first,F[0][i].second,1);
		updset(0,cnt,y,F[1][i].first,F[1][i].second,1);
	}
	build(0,cnt,1);
	updset(0,cnt,0,0,1,1);
	for(int i=n;i;i--)
	{
		int x=P[i].first,y=P[i].second;
		node f1=get(0,cnt,0,x-1,1);
		node f2=get(0,cnt,0,y-1,1);
		update(0,cnt,0,x-1,0,1);
		update(0,cnt,x+1,y-1,1,1);
		update(0,cnt,y+1,cnt,2,1);
		G[0][i]={(f1.sum+f1.cnt*A[i].first)%mod,f1.cnt};
		G[1][i]={(f2.sum+f2.cnt*A[i].second)%mod,f2.cnt};
		updset(0,cnt,x,G[0][i].first,G[0][i].second,1);
		updset(0,cnt,y,G[1][i].first,G[1][i].second,1);
	}
	long long ans=0,pw=1;
	for(int i=1;i<n;i++) pw=pw*2%mod;
	for(int i=1;i<=n;i++)
	{
		ans=(ans+F[0][i].first*G[0][i].second%mod+F[0][i].second*G[0][i].first%mod-F[0][i].second*G[0][i].second%mod*A[i].first%mod+mod)%mod;
		ans=(ans+F[1][i].first*G[1][i].second%mod+F[1][i].second*G[1][i].first%mod-F[1][i].second*G[1][i].second%mod*A[i].second%mod+mod)%mod;
		ans=(ans-(A[i].first+A[i].second)%mod*pw%mod+mod)%mod;
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:109:34: warning: narrowing conversion of 'A[i].std::pair<long long int, long long int>::first' from 'long long int' to 'int' [-Wnarrowing]
  109 |                 val[++cnt]={A[i].first,i,0},val[++cnt]={A[i].second,i,1};
      |                             ~~~~~^~~~~
Main.cpp:109:62: warning: narrowing conversion of 'A[i].std::pair<long long int, long long int>::second' from 'long long int' to 'int' [-Wnarrowing]
  109 |                 val[++cnt]={A[i].first,i,0},val[++cnt]={A[i].second,i,1};
      |                                                         ~~~~~^~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 30 / 30