Submission #906588

#	Time	Username	Problem	Language	Result	Execution time	Memory
906588		Nonoze	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	26 ms	7632 KiB

fancyfence

#include <bits/stdc++.h>

#define int long long
#define sz(x) (int)(x.size())

using namespace std;

const int mod=1000000007;

int MOD(int x) {
	return (x+3*mod)%mod;
}

struct sections {
	int H=0, W=0;
};

int n, k, m;
vector<sections> a;

int section(int h, int w) {
	h%=mod, w%=mod;
	int facteur=MOD((h*(h+1))/2);
	int ans=MOD((w*(w+1))/2);
	return MOD(ans*facteur);
}

int full() {
	int ans=0;
	vector<int> l(n, 0);
	vector<int> r(n, 0);
	vector<int> prefix(n, 0);
	stack<pair<int, int>> stk;
	for (int i=0; i<n; i++) {
		while (!stk.empty() && stk.top().first >= a[i].H) stk.pop();
		if (!stk.empty()) l[i]=stk.top().second+1; // Je supprime une fois de torp ->  Je dois faire -1
		else l[i]=0; // Tout est parti -> je prends depuis le début
		stk.push({a[i].H, i});
		if (i) prefix[i]=prefix[i-1]; // PREFIX SUM
		prefix[i]= MOD(prefix[i]+a[i].W);
	}
	while (!stk.empty()) stk.pop();
	for (int i=n-1; i>=0; i--) {
		while (!stk.empty() && stk.top().first > a[i].H) stk.pop();
		if (!stk.empty()) r[i]=stk.top().second-1; //Je retire une fois de trop -> Donc je dois faire -1
		else r[i]=n-1; // Tout est parti -> je prends depuis la fin
		stk.push({a[i].H, i});
	}
	for (int i=0; i<n; i++) {
		int suml=0, sumr=0;
		if (i>0) suml=MOD(prefix[i-1]-(l[i]>0?prefix[l[i]-1]:0)); // SOMME DROITE
		if (r[i]>=0) sumr=MOD(prefix[r[i]]-prefix[i]); // SOMME GAUCHE
		int sumw=suml+sumr+a[i].W; // Largeure totale du rectangle
		int sum=MOD(section(a[i].H, sumw)-section(a[i].H, suml)-section(a[i].H, sumr)); //Si je prends tout - je prends pas 2 fois gauche/droite

		ans=MOD(ans+sum);
	}
	return ans;
}

int solve() {
	cin >> n;
	a.clear();
	a.resize(n);
	for (auto &u: a) cin >> u.H;
	for (auto &u: a) cin >> u.W;
	vector<sections> temp;
	for (int i=0; i<n; i++) {
		if (!temp.empty() && a[i].H==temp.back().H) temp.back().W+=a[i].W;
		else temp.push_back(a[i]);
		a[i].W%=mod;
	}
	a.clear();
	a=temp;
	n=a.size();
	return full();
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout << solve() << endl;
	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