Submission #292923

#	Time	Username	Problem	Language	Result	Execution time	Memory
292923		arnold518	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	86 ms	7544 KiB

fancyfence

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const ll INF = 1e18;
const ll MOD = 1e9+7;

int N;
ll W[MAXN+10], H[MAXN+10];

pll tree[MAXN*4+10];

void init(int node, int tl, int tr)
{
	if(tl==tr)
	{
		tree[node]={H[tl], tl};
		return;
	}
	int mid=tl+tr>>1;
	init(node*2, tl, mid);
	init(node*2+1, mid+1, tr);
	tree[node]=min(tree[node*2], tree[node*2+1]);
}

pll query(int node, int tl, int tr, int l, int r)
{
	if(l<=tl && tr<=r) return tree[node];
	if(r<tl || tr<l) return {INF, -1};
	int mid=tl+tr>>1;
	return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
	
ll ans=0;

ll f(ll x)
{
	x%=MOD;
	return x*(x+1)%MOD*((MOD+1)/2)%MOD;
}

ll f(ll l, ll r)
{
	return ((f(r)-f(l))%MOD+MOD)%MOD;
}

void solve(int l, int r, ll h)
{
	if(l>r) return;
	pll p=query(1, 1, N, l, r);

	ans+=f(h, p.first)*f(0, W[r]-W[l-1])%MOD;
	ans%=MOD;

	solve(l, p.second-1, p.first);
	solve(p.second+1, r, p.first);
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%lld", &H[i]);
	for(int i=1; i<=N; i++) scanf("%lld", &W[i]), W[i]+=W[i-1];

	init(1, 1, N);
	solve(1, N, 0);
	printf("%lld\n", ans);
}

Compilation message (stderr)

fancyfence.cpp: In function 'void init(int, int, int)':
fancyfence.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |  int mid=tl+tr>>1;
      |          ~~^~~
fancyfence.cpp: In function 'pll query(int, int, int, int, int)':
fancyfence.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |  int mid=tl+tr>>1;
      |          ~~^~~
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
fancyfence.cpp:66:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  for(int i=1; i<=N; i++) scanf("%lld", &H[i]);
      |                          ~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp:67:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  for(int i=1; i<=N; i++) scanf("%lld", &W[i]), W[i]+=W[i-1];
      |                          ~~~~~^~~~~~~~~~~~~~~

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