Submission #646976

#	Time	Username	Problem	Language	Result	Execution time	Memory
646976		jamielim	Fancy Fence (CEOI20_fancyfence)	C++14	30 / 100	58 ms	20288 KiB

fancyfence

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

#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ii,ii> i4;
const int MOD=1000000007;
const int INF=1012345678;
const ll LLINF=1012345678012345678LL;
const double PI=3.1415926536;
const double EPS=1e-14;

int n;
int h[100005],w[100005];

ll choose2(ll x){
	return ((x)*(x-1)/2)%MOD;
}

struct node{
	int s,e,m;
	ll ht,wd,val;
	ll lzht;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;
		if(s==e){
			ht=h[s];
			wd=w[s];
			val=(wd*choose2(ht+1))%MOD;
		}else{
			l=new node(s,m);
			r=new node(m+1,e);
			ht=min(l->ht,r->ht);
			wd=l->wd+r->wd;
			val=l->val+r->val;
		}
	}
	void laze(){
		if(s!=e){
			l->lzht=lzht;
			r->lzht=lzht;
		}
		ht=lzht;
		val=(wd*choose2(ht+1))%MOD;
	}
	void upd(int x,int y,ll v){ // set height to be v for indices in [x,y]
		if(y<s||x>e||x>y)return;
		//printf("%d %d %lld\n",x,y,v);
		if(s<=x&&e<=y){
			lzht=v;
			laze();
			return;
		}
		laze();
		if(y<=m)l->upd(x,y,v);
		else if(x>m)r->upd(x,y,v);
		else l->upd(x,m,v),r->upd(m+1,y,v);
		l->laze();r->laze();
		ht=min(l->ht,r->ht);
		val=l->val+r->val;
	}
	ll qry(int x){ // sum of wd*((ht+1)C2) for indices <=x
		//printf("%d\n",x);
		if(x<s)return 0;
		if(s==e)return val;
		if(x<=m)return l->qry(x);
		return (l->val+r->qry(x))%MOD;
	}
}*root;

int main(){
	scanf("%d",&n);
	vector<int> v;
	for(int i=0;i<n;i++){
		scanf("%d",&h[i]);
		v.pb(h[i]);
	}
	for(int i=0;i<n;i++)scanf("%d",&w[i]);
	root=new node(0,n-1);
	ll ans=0;
	vector<ii> stk;
	stk.pb(-1,-1);
	for(int i=0;i<n;i++){
		// find leftmost value that is > h[i] and index <i
		int x=i;
		while(stk.back().fi>h[i]){
			x=stk.back().se;
			stk.pop_back();
		}
		stk.pb(h[i],i);
		root->upd(x,i-1,h[i]);
		
		ll cur=(root->qry(i-1))*(ll)(w[i]);
		cur%=MOD;
		ans+=cur; // left side is strictly from previous block, right side is (,] of current block
		ans%=MOD;
		ans+=((choose2(h[i]+1))*(choose2(w[i]+1)))%MOD; // left side is within current block
		ans%=MOD;
	}
	printf("%lld",ans%MOD);
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fancyfence.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |   scanf("%d",&h[i]);
      |   ~~~~~^~~~~~~~~~~~
fancyfence.cpp:85:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |  for(int i=0;i<n;i++)scanf("%d",&w[i]);
      |                      ~~~~~^~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 12
• Subtask 3: 0 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27