Submission #667552

#	Time	Username	Problem	Language	Result	Execution time	Memory
667552		dozer	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	83 ms	11168 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define endl "\n"
#define sp " "
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define L(node) node * 2
#define R(node) node * 2 + 1
#define int long long

const int INF = 1e9 + 7;
const int modulo = 1e9 + 7;


int h[N], w[N], pre[N];
pii tree[N * 4];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = {h[l], l};
		return;
	}
	int mid = (l + r) / 2;
	build(L(node), l, mid);
	build(R(node), mid + 1, r);
	tree[node] = min(tree[L(node)], tree[R(node)]);
}


pii find(int node, int l, int r, int sl, int sr)
{
	if (l > r || l > sr || r < sl) return {INF, INF};
	if (l >= sl && r <= sr) return tree[node];
	int mid = (l + r) / 2;
	return min(find(L(node), l, mid, sl, sr), find(R(node), mid + 1, r, sl, sr));
}

int ans, n;

int add(int a, int b)
{
	if (a + b < modulo) return a + b;
	return a + b - modulo;
}

int mul(int a, int b)
{
	return (a * b) % modulo;
}


int subs(int a, int b)
{
	if (a < b) return a - b + modulo;
	return a - b;
}

int fe(int a, int b)
{
	if (b == 0) return 1;
	if (b % 2) return mul(a, fe(a, b - 1));
	int tmp = fe(a, b / 2);
	return mul(tmp, tmp);
}


void f(int l, int r, int prev)
{
	pii tmp = find(1, 1, n, l, r);
	//cout<<l<<sp<<r<<sp<<tmp.st<<sp<<tmp.nd<<endl;
	int maks = tmp.st;
	int ind = tmp.nd;
	int sum = subs(pre[r], pre[l - 1]);
	int x = mul(sum, sum + 1);
	//cout<<x<<sp;
	x = mul(x, fe(2, modulo - 2));
	//cout<<x<<sp;
	int hig = mul(mul(maks, maks + 1), fe(2, modulo - 2));
	int no = mul(mul(prev, prev + 1), fe(2, modulo - 2));
	x = mul(x, subs(hig, no));
	if (maks != prev) ans = add(ans, x);
	if (ind > l) f(l, ind - 1, maks);
	if (ind < r) f(ind + 1, r, maks);
}

int32_t main()
{
	//fileio();
	fastio();

	cin>>n;
	for (int i = 1; i <= n; i++)
		cin>>h[i];
	for (int j = 1; j <= n; j++)
	{
		cin>>w[j];
		pre[j] = add(pre[j - 1], w[j]);
	}
	build(1, 1, n);
	f(1, n, 0);
	cout<<ans<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

• 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