Submission #944854

#	Time	Username	Problem	Language	Result	Execution time	Memory
944854		oolimry	Fancy Fence (CEOI20_fancyfence)	C++17	12 / 100	1 ms	856 KiB

fancyfence

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define h first
#define w second
using namespace std;
typedef long long lint;
typedef pair<lint,lint> ii;

lint H[100005];
lint W[100005];
lint mod = 1000000007;

void fix(lint &x){
	x %= mod;
	if(x < 0) x += mod;
}

lint within(lint h, lint w){
	lint A = h * (h+1) / 2;
	fix(A);
	
	lint B = w * (w + 1) / 2;
	fix(B);
	
	return (A*B)%mod;
}

lint acc = 0; ///sum of h*(h+1)*w of previous blocks
lint ans = 0; 

vector<ii> S;

lint cal(lint h, lint w){
	lint toadd = h*(h+1)/2;
	fix(toadd);
	toadd *= w;
	fix(toadd);
	return toadd;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	
	for(int i = 0;i < n;i++) cin >> H[i];
	for(int i = 0;i < n;i++) cin >> W[i];	
	
	for(int i = 0;i < n;i++){
		lint h = H[i], w = W[i];
		assert(w == 1);
		
		lint popWidth = 0;
		while(!S.empty()){
			ii T = S.back();
			if(T.h > h){
				popWidth += T.w;
				S.pop_back();
				acc -= cal(T.h, T.w);
				fix(acc);
			}
			else break;
		}
		
		fix(popWidth);
		
		acc += cal(h, popWidth);
		fix(acc);
		
		ans += acc * w;
		ans += within(h,w);
		fix(ans);
		
		popWidth += w;
		fix(popWidth);
		
		S.push_back(ii(h, popWidth));
		acc += cal(h,w);
		fix(acc);
		
	}
	
	cout << ans << "\n";
	
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 0 / 13
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 18
• Subtask 7: 0 / 27