Submission #1329590

#TimeUsernameProblemLanguageResultExecution timeMemory
1329590prism7kFancy Fence (CEOI20_fancyfence)C++20
100 / 100
19 ms2756 KiB
#include <bits/stdc++.h>
using namespace std;

const long long mod = 1e9+7;

long long add(long long a, long long b) {
	return (a + b) % mod;
}

long long mult(long long a) {
	return ((a * (a + 1)) / 2) % mod;
}

long long comb(long long h, long long w) {
	return (mult(h) * mult(w)) % mod;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n; cin >> n;
	vector<int> widths(n), heights(n);
	for(int &x : heights) cin >> x;
	for(int &x : widths) cin >> x;
	long long res = 0;
	
	stack<pair<long long, long long>> s;
	s.push({0,0});
	for(int i = 0; i < n; ++i) {
		long long h = heights[i], w = widths[i];
		// merge until monotonic again
		while(true) {
			long long pos = 0, neg = 0;
			if(h > s.top().second) {
				s.push({w, h});
				break;
			} else {
				long long ph = s.top().second;
				long long pw = s.top().first;
				s.pop();
				if(s.top().second < h) {
					pos = comb(ph, pw);
					neg = comb(h, pw);
					s.push({add(pw, w), h});
					res = add(res, ((pos - neg) + mod) % mod);
					break;
				} else {
					pos = comb(ph, pw);
					neg = comb(s.top().second, pw);
					s.top().first = add(s.top().first, pw);
					res = add(res, ((pos - neg) + mod) % mod);
				}
			}
		}
	}
	while((int)s.size() > 1) {
		long long cur_w = s.top().first;
		long long cur_h = s.top().second;
		s.pop();
		long long prev_h = s.top().second;
		long long pos = comb(cur_h, cur_w);
		long long neg = comb(prev_h, cur_w);
		res = add(res, ((pos - neg) + mod) % mod);
		s.top().first = add(s.top().first, cur_w);
	}
	cout << res << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...