Submission #1267219

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267219		dio_2	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	29 ms	3404 KiB

fancyfence

#include<bits/stdc++.h>

const int MOD = int(1e9) + 7;
const int64_t INV_2 = 500000004;

int64_t f(int a, int b){
	assert(a>=0);
	assert(b>=0);
	int res =  int64_t(a) * (a + 1) % MOD * INV_2 % MOD * int64_t(b) % MOD * (b + 1) % MOD * INV_2 % MOD;
	//~ assert(res >= 0);
	return res;
}

int main(){
	using namespace std;
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	int n;
	cin >> n;
	
	vector<int> h(n), w(n);
	int all_1 = 1;
	for(int i = 0;i < n;i++) cin >> h[i];
	for(int i = 0;i < n;i++) {
		cin >> w[i];
		all_1 &= (w[i] == 1);
	}
	
	int64_t ans = 0;
	
	vector<int64_t> psw(n);
	for(int i = 0;i < n;i++){
		psw[i] = w[i] + (i > 0 ? psw[i - 1] : 0);
	}
	
	vector<int> lew(n), praw(n);
	// lew[i] I CARE ABOUT FIRST < ME
	
	vector<int> st;
	for(int i = 0;i < n;i++){
		while(!st.empty() && h[st.back()] >= h[i]) st.pop_back();
		lew[i] = (!st.empty() ? st.back()+1 : 0);
		st.push_back(i);
	}
	
	st.clear();
	for(int i = n - 1;i >= 0;i--){
		while(!st.empty() && h[st.back()] > h[i]) st.pop_back();
		praw[i] = (!st.empty() ? st.back()-1 : n-1);
		st.push_back(i);
	}
	
	for(int i = 0;i < n;i++){
		int64_t sL = 0;
		int64_t sR = 0;
		int l = lew[i];
		int r = praw[i];
		/*
		while(l - 1 >= 0 && h[l - 1] >= h[i]){
			l -= 1;
			sL += w[l];
		}
		while(r + 1 < n && h[r + 1] > h[i]){
			r += 1;
			sR += w[r];
		}
		*/
		//~ cerr << "i: " << i << " l: " << l << " r: " << r << endl;
		sL = psw[i] - (l > 0 ? psw[l-1] : 0) - w[i];
		sR = psw[r] - psw[i];
		// but it must strictly contain me
		assert(sL>=0);
		assert(sR>=0);
		sL %= MOD;
		sR %= MOD;
		if(w[i] == 1){
			ans += f(h[i], w[i]) * int64_t(sL+1) % MOD * int64_t(sR+1) % MOD;
			ans %= MOD;
		}
		else {
			// w[i] > 1
			// 1) touching with left side
			ans += (w[i] - 1) * 1ll * (sL+1) % MOD * f(h[i], 1) % MOD;
			ans %= MOD;
			// 2) touching with the right side
			ans += (w[i] - 1) * 1ll * (sR+1) % MOD * f(h[i], 1) % MOD;
			ans %= MOD;
			// 3) touching both sides
			ans += f(h[i],1) * 1ll * (sR+1) % MOD * (sL+1) % MOD;
			ans %= MOD;
			// 4) not touching any side
			if(w[i] > 2){
				ans += f(h[i], w[i] - 2) % MOD;
				ans %= MOD;
			}
		}
	}
	
	cout << ans%MOD << '\n';
	
	return 0;
}

• 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