Submission #1340730

#TimeUsernameProblemLanguageResultExecution timeMemory
1340730onur8ocakFancy Fence (CEOI20_fancyfence)C++20
0 / 100
2 ms360 KiB
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <set>
#include <map>

using namespace std;
#define fio() ios_base::sync_with_stdio(false);  cin.tie(NULL);
#define debug(x) cout << x << " ABC " << endl
#define int long long
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second

const int INF = 1e18;
const int MOD = 1e9 + 7;

int gauss(int x){		
	return (x * (x + 1)) / 2;
}

struct SegTree{
	int n;
	vector<int> tree;
	
	SegTree(vector<int> &a){
		n = a.size() - 10;
		tree.assign(4 * n + 100, INF);
		build(1, 1, n, a);
	}
	
	void build(int node, int tl, int tr, vector<int> &a){
		if(tl == tr){
			tree[node] = a[tl];
			return;
		}
		int tm = (tl + tr) / 2;
		build(node * 2, tl, tm, a);
		build(node * 2 + 1, tm + 1, tr, a);
		tree[node] = min(tree[node*2], tree[node*2+1]);
	}
	
	int query(int node, int l, int r, int tl, int tr){
		if(r < tl || tr < l) return INF;
		if(l <= tl && tr <= r) return tree[node];
		int tm = (tl + tr) / 2;
		return min(query(node * 2, l, r, tl, tm), query(node * 2 + 1, l, r, tm + 1, tr)); 
	}
};

void _(){
	int n; 
	cin >> n;
	vector<int> h(n+10), w(n+10);
	for(int i = 1; i <= n; i++) cin >> h[i];
	for(int i = 1; i <= n; i++) cin >> w[i];
	SegTree st(h);
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i; j <= n; j++){
			if(i == j){ 
				int inc = (gauss(h[i]) * gauss(w[i]));
				inc = inc % MOD;
				ans = (ans + inc);
				ans = ans % MOD;
			}
			else{
				int sm = st.query(1, 1, n, i, j);
				sm = gauss(sm);
				sm = sm * w[i];
				sm = sm % MOD;
				sm = sm * w[j];
				sm = sm % MOD;
				ans += sm;
			}
		}
	}
	cout << ans << endl;
	
}		

int32_t main(){
	fio()
	int tc = 1;
	//cin >> tc;
	while(tc--) _();
	return 0;
}

#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...