Submission #447882

#	Time	Username	Problem	Language	Result	Execution time	Memory
447882		flappybird	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	154 ms	13916 KiB

fancyfence

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 101010
#define MOD 1000000007
#define ln '\n'
ll H[MAX], W[MAX];
ll sw[MAX];
ll ans = 0;
ll N;
struct segtree {
	ll N, s;
	vector<pll> tree;
	vector<ll> l, r;
	void init(ll x = 1) {
		if (x >= s) {
			l[x] = r[x] = x - s + 1;
			if (x - s + 1 > N) tree[x] = { INT32_MAX, l[x] };
			tree[x].second = l[x];
			return;
		}
		init(x * 2);
		init(x * 2 + 1);
		l[x] = l[x * 2];
		r[x] = r[x * 2 + 1];
		tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
	}
	segtree(ll n) {
		N = n;
		s = 1LL << (ll)ceil(log2(N));
		tree.resize(2 * s + 1);
		l.resize(2 * s + 1);
		r.resize(2 * s + 1);
	}
	segtree() {}
	pll query(ll low, ll high, ll loc = 1) {
		if (l[loc] == low && r[loc] == high) return tree[loc];
		if (r[loc * 2] >= high) return query(low, high, loc * 2);
		if (l[loc * 2 + 1] <= low) return query(low, high, loc * 2 + 1);
		return min(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
	}
};
segtree seg;
void get(ll l, ll r) {
	if (l > r) return;
	ll res = seg.query(l, r).second;
	ll a = sw[r] - sw[l - 1];
	a %= MOD;
	ll b = H[res];
	b %= MOD;
	ll ls, rs;
	ls = sw[res] - sw[l - 1] - W[res];
	ls %= MOD;
	rs = sw[r] - sw[res];
	rs %= MOD;
	ll mem = a * (a + 1);
	mem %= MOD;
	mem -= ls * (ls + 1);
	mem %= MOD;
	mem -= rs * (rs + 1);
	mem %= MOD;
	mem *= b;
	mem %= MOD;
	mem *= (b + 1);
	mem %= MOD;
	while (mem % 4) mem += MOD;
	mem /= 4;
	ans += mem;
	ans %= MOD;
	get(l, res - 1);
	get(res + 1, r);
}
signed main() {
	ll N;
	cin >> N;
	ll i;
	seg = segtree(N);
	for (i = 1; i <= N; i++) cin >> H[i];
	for (i = 1; i <= N; i++) cin >> W[i], sw[i] = sw[i - 1] + W[i];
	for (i = 1; i <= N; i++) seg.tree[i + seg.s - 1] = { H[i], i };
	seg.init();
	get(1, N);
	ans %= MOD;
	if (ans < 0) ans += MOD;
	cout << ans << ln;
}

• 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