Submission #397128

#	Time	Username	Problem	Language	Result	Execution time	Memory
397128		Sohsoh84	Fancy Fence (CEOI20_fancyfence)	C++14	15 / 100	91 ms	17020 KiB

fancyfence

#include <bits/stdc++.h>

using namespace std;

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

#define all(x)                      (x).begin(),(x).end()
#define X                           first
#define Y                           second
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; // 998244353; // 1e9 + 9;
const ll INV2 = 500000004;

ll L[MAXN], H[MAXN], W[MAXN];
set<pll> st;

inline void mkey(ll& a) {
	if (a >= MOD) a -= MOD;
	if (a < 0) a += MOD;
}

inline ll C2(ll a) {
	a %= MOD;
	return a * (a - 1) % MOD * INV2 % MOD;;
} 

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	vector<int> v;
	for (int i = 1; i <= n; i++) {
		cin >> H[i];
		v.push_back(i);
	}

	L[0] = 1;
	ll tot = 0;
	for (int i = 1; i <= n; i++) {
		cin >> W[i];
		L[i] = L[i - 1] + W[i - 1];
		tot += W[i];
	}

	ll T = C2(tot + 1);
	st.insert({1, tot});

	sort(all(v), [] (int i, int j) {
		return H[i] < H[j];		
	});


	ll lst = 0, ans = 0;
	for (int e : v) {
		mkey(ans += T * (C2(H[e] + 1) - C2(lst + 1) + MOD) % MOD);
		ll l = L[e], r = l + W[e] - 1;
		auto it = st.upper_bound(make_pair(l, INF));
		it--;
		ll tl = it -> X, tr = it -> Y;
		mkey(T -= C2(tr - tl + 2));
		ll m_r = l - 1, m_l = r + 1;
		
		if (m_r >= tl) {
			mkey(T += C2(m_r - tl + 2));
			st.insert({tl, m_r});
		} 

		if (m_l <= tr) {
			mkey(T += C2(tr - m_l + 2));
		       	st.insert({m_l, tr});	
		}

		lst = H[e];
	}

	cout << ans << endl;
	return 0;
}

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