Submission #959940

#	Time	Username	Problem	Language	Result	Execution time	Memory
959940		penguin133	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	230 ms	42184 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair <int, int> 
#define pii pair <int, pi>

int n, H[1000005], W[1000005], P[1000005], A[100005];
stack <pi> s;
const int mod = 1e9 + 7;
vector <int> v;
struct node{
	int s, e, m, val, lz, val2;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1;
		val = lz = val2 = 0;
		l = r = nullptr;
	}
	
	void mc(){
		if(s == e || l != nullptr)return;
		l = new node(s, m);
		r = new node(m+1, e);
	}
	
	void prop(){
		if(lz){
			int brr = v[e] * (v[e] + 1) / 2;
			brr %= mod;
			int brr2 = v[s - 1] * (v[s - 1] + 1) / 2;
			brr2 %= mod;
			brr = (brr - brr2 + mod) % mod;
			val = lz * (brr) % mod;
			if(s != e){
				mc();
				l->lz = lz; r->lz = lz;
			}
			lz = 0;
		}
	}
	
	void upd(int a, int b, int c){
		if(a > b)return;
		prop();
		if(a == s && b == e)lz = c;
		else{
			mc();
			if(b <= m)l->upd(a, b, c);
			else if(a > m)r->upd(a, b, c);
			else l->upd(a, m, c), r->upd(m+1, b, c);
			l->prop(), r->prop();
			val = l->val + r->val;
			val %= mod;
		}
	}
	
	int qry(int a, int b){
		if(a > b)return 0;
		prop();
		if(a == s && b == e)return val;
		if(l == nullptr)return 0;
		if(b <= m)return l->qry(a, b);
		if(a > m)return r->qry(a, b);
		return (l->qry(a, m) + r->qry(m+1, b)) % mod;
	}
}*root;

void solve(){
	cin >> n;
	v.push_back(1e9);
	v.push_back(0);
	for(int i = 1; i <= n; i++)cin >> H[i], v.push_back(H[i]), v.push_back(H[i] + 1);
	for(int i = 1; i <= n; i++)cin >> W[i];
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	root = new node(1, (int)v.size());
	s.push({0, 0});
	int ans = 0;
	root = new node(0, 1e9);
	for(int i = 1; i <= n; i++){
		P[i] = P[i - 1] + W[i];
		P[i] %= mod;
		int x = lower_bound(v.begin(), v.end(), H[i] + 1) - v.begin();
		root->upd(x, (int)v.size(), P[i]);
		//for(int j = H[i] + 1; j <= 100; j++)lst[j] = P[i];
		/*
		for(int j = 1; j <= H[i]; j++){
			ans += j * W[i] % mod * (P[i - 1] - lst[j] + mod) % mod;
			ans %= mod;
		}
		*/
		root->prop();
		x--;
		int tot = root->qry(1, x);
		int tot2 = H[i] * (H[i] + 1) / 2;
		tot2 %= mod;
		tot2 *= P[i - 1];
		tot2 %= mod;
		tot2 -= tot;
		tot2 = (tot2 + mod) % mod;
		ans += tot2 * W[i] % mod;
		ans %= mod;
		int a = W[i] * (W[i] + 1) / 2;
		a %= mod;
		int b = H[i] * (H[i] + 1) / 2;
		b %= mod;
		ans += (a * b % mod);
		ans %= mod;
		//cout << ans << '\n';
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	while(tc--)solve();
}

Compilation message (stderr)

fancyfence.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~

• 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