Submission #298997

#	Time	Username	Problem	Language	Result	Execution time	Memory
298997		square1001	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	114 ms	4984 KiB

fancyfence

#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> H(N), W(N);
	for(int i = 0; i < N; ++i) cin >> H[i];
	for(int i = 0; i < N; ++i) cin >> W[i];
	vector<int> WS(N + 1);
	for(int i = 0; i < N; ++i) {
		WS[i + 1] = WS[i] + W[i];
		if(WS[i + 1] >= mod) WS[i + 1] -= mod;
	}
	vector<int> perm(N);
	for(int i = 0; i < N; ++i) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return H[i] > H[j]; });
	set<pair<int, int> > s;
	long long current = 0;
	int ans = 0;
	for(int i = 0; i < perm.size(); ++i) {
		int id = perm[i];
		current = (current + 1LL * W[id] * (W[id] + 1)) % mod;
		set<pair<int, int> >::iterator it = s.lower_bound(make_pair(id, -1));
		int cl = id, cr = id + 1;
		if(it != s.end()) {
			if(it->first == cr) {
				// connect!
				current -= 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				current -= 1LL * (WS[it->second] - WS[it->first] + mod) * (WS[it->second] - WS[it->first] + mod + 1) % mod;
				cr = it->second;
				current += 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				it = s.erase(it);
			}
		}
		if(it != s.begin()) {
			--it;
			if(it->second == cl) {
				// connect!
				current -= 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				current -= 1LL * (WS[it->second] - WS[it->first] + mod) * (WS[it->second] - WS[it->first] + mod + 1) % mod;
				cl = it->first;
				current += 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				it = s.erase(it);
			}
		}
		s.insert(make_pair(cl, cr));
		while(current < 0) current += mod;
		while(current >= mod) current -= mod;
		int hr = H[perm[i]], hl = (i + 1 != N ? H[perm[i + 1]] : 0);
		int hc = (1LL * hr * (hr + 1) / 2 - 1LL * hl * (hl + 1) / 2) % mod;
		int sub = 1LL * current * hc % mod;
		ans = (ans + sub) % mod;
	}
	ans = 1LL * ans * (mod / 2 + 1) % mod;
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < perm.size(); ++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