Submission #945756

#	Time	Username	Problem	Language	Result	Execution time	Memory
945756		kxd	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	28 ms	7008 KiB

fancyfence

#include <bits/stdc++.h>
//#define DEBUG 1106
#define int long long
#define ll long long
#define ld long double
#define pb push_back
#define p_q priority_queue
#define m_p make_pair
#define pii pair<int,int>
#define endl '\n'
#define INIT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FOR(i,a,b) for(int i = a; i <= b; i++)
#define forn(i,n) for (int i = 0; i < n; i++)
#define forn1(i,n) for (int i = 1; i <= n; i++)
#define all(x) x.begin(),x.end()
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)
#ifdef DEBUG
#define debug(x) cout << #x << ": " << x << endl;
#else
#define debug(x) 1106;
#endif

using namespace std;
const int N = 2e5+5;
const int inf = 1e9;
const int INF = 1e18;
const int MOD = 1e9+7;
const int mod = 1e9+7;

int h[N], w[N];

int f(int x) {
	return (x*(x+1)/2)%mod;
}

signed main() {
	INIT
	#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	#endif
	///////////
	int n;
	cin >> n;
	forn(i,n) cin >> h[i];
	forn(i,n) cin >> w[i];
	int ans = 0;
	int sum = 0;
	stack<tuple<int,int,int>> st;
	forn(i,n) {
		ans += f(h[i])*f(w[i]) % mod;
			ans %= mod;
		int m = 0;
		while (st.size() && get<0>(st.top()) >= h[i]){
			auto [h,w,p] = st.top();
			st.pop();
			m += w;
				m %= mod;
			sum = (sum-p + mod);
				sum %= mod;
		}
		ans += sum*w[i] %mod;
			ans %= mod;
		ans += m*f(h[i])%mod * w[i]%mod;
			ans %= mod;
		m += w[i];
			m %= mod;
		int t = m*f(h[i]);
			t %= mod;
		sum += t;
			sum %= mod;
		st.push({h[i], m, t});
	}
	cout << ans %mod;
}

• 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