Submission #534872

#	Time	Username	Problem	Language	Result	Execution time	Memory
534872		ComPhyPark	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	372 ms	22344 KiB

fancyfence

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll M = 1000000007;
ll n;
ll h[101010], w[101010];
ll hst[303030], wst[303030];
void hinit(ll l, ll r, ll id) {
	if (l == r) {
		hst[id] = h[l];
		return;
	}
	ll m = (l + r) / 2;
	hinit(l, m, 2 * id);
	hinit(m + 1, r, 2 * id + 1);
	hst[id] = min(hst[2 * id], hst[2 * id + 1]);
}
void winit(ll l, ll r, ll id) {
	if (l == r) {
		wst[id] = w[l];
		return;
	}
	ll m = (l + r) / 2;
	winit(l, m, 2 * id);
	winit(m + 1, r, 2 * id + 1);
	wst[id] = wst[2 * id] + wst[2 * id + 1];
}
ll hqry(ll l, ll r, ll id, ll s, ll e) {
	if (l > e || s > r)return M;
	if (s <= l && r <= e)return hst[id];
	ll m = (l + r) / 2;
	return min(hqry(l, m, 2 * id, s, e), hqry(m + 1, r, 2 * id + 1, s, e));
}
ll wqry(ll l, ll r, ll id, ll s, ll e) {
	if (l > e || s > r)return 0;
	if (s <= l && r <= e)return wst[id];
	ll m = (l + r) / 2;
	return wqry(l, m, 2 * id, s, e) + wqry(m + 1, r, 2 * id + 1, s, e);
}
ll f(ll s, ll e, ll t) {
	if (s > e)return 0;
	ll mh = hqry(0, n - 1, 1, s, e);
	if (mh == t) {
		ll l = s, r = e, m;
		while (l < r) {
			m = (l + r) / 2;
			if (hqry(0, n - 1, 1, s, m) == t) {
				r = m;
			}
			else {
				l = m + 1;
			}
		}
		return (f(s, l - 1, t) + f(l + 1, e, t)) % M;
	}
	else {
		ll hn = (mh * (mh + 1) - t * (t + 1)) / 2;
		hn %= M;
		ll ws = wqry(0, n - 1, 1, s, e) % (2 * M), wn = ws * (ws + 1) / 2 % M;
		ll r = wn * hn % M;
		return (r + f(s, e, mh)) % M;
	}
}
int main() {
	ll i;
	scanf("%lld", &n);
	for (i = 0; i < n; i++) {
		scanf("%lld", &h[i]);
	}
	for (i = 0; i < n; i++) {
		scanf("%lld", &w[i]);
	}
	hinit(0, n - 1, 1);
	winit(0, n - 1, 1);
	printf("%lld", f(0, n - 1, 0));
	return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%lld", &n);
      |  ~~~~~^~~~~~~~~~~~
fancyfence.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   scanf("%lld", &h[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
fancyfence.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%lld", &w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• 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