Submission #813035

#	Time	Username	Problem	Language	Result	Execution time	Memory
813035		ezdp	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	108 ms	30796 KiB

fancyfence

#include<bits/stdc++.h>
 
#define endl '\n'
#define fr first
#define sc second
#define ll long long int
 
const int MAXN = 1e5;
const int MAXL = 20;
const ll MOD = 1e9 + 7;
 
inline std::pair<int, int> my_min(const std::pair<int, int> &a, const std::pair<int, int> &b){
	if(a.fr < b.fr) return a;
	if(a.fr > b.fr) return b;
	if(a.sc < b.sc) return a;
	return b;
}
 
inline ll mult(ll a, ll b){
	return (a * b) % MOD;
}
 
inline ll fp(ll b, ll p){
	if(p == 0) return 1LL;
	if(p == 1) return b;
	if(p & 1) return mult(b, fp(b, p - 1));
	ll aux = fp(b, p / 2);
	return mult(aux, aux);
}
 
inline ll divi(ll a, ll b){
	return mult(a, fp(b, MOD - 2));
}
 
inline ll f(ll n){
	n = (n + MOD) % MOD;
	return divi(mult(n, n + 1), 2);
}
 
int lg2[MAXN + 5];
ll N, h[MAXN + 5], w[MAXN + 5], prefw[MAXN + 5];
std::pair<int, int> sparse[MAXN + 5][MAXL + 1];
 
std::pair<int, int> get(int l, int r){
	int j = lg2[r - l + 1];
	return my_min(sparse[l][j], sparse[r - (1 << j) + 1][j]);
}
 
ll rec(int l = 1, int r = N){
	if(l > r) return 0;
	int minh = get(l, r).fr, id = l;
	ll my_ans = 0, other_ans = 0;
	my_ans = mult(f(minh), f(prefw[r] - prefw[l - 1]));
	while(true){
		auto [myh, myid] = get(id, r);
		if(myh != minh){
			my_ans = (my_ans - mult(f(minh), f(prefw[r] - prefw[id - 1])) + MOD) % MOD;
			other_ans += rec(id, r);
			break;
		}
		else{
			my_ans = (my_ans - mult(f(minh), f(prefw[myid - 1] - prefw[id - 1])) + MOD) % MOD;
			other_ans += rec(id, myid - 1);
			id = myid + 1;
		}
	}
	my_ans %= MOD;
	other_ans %= MOD;
	return (my_ans + other_ans) % MOD;
}
 
inline void init(){
	lg2[1] = 0;
	for(int i = 2; i <= MAXN; ++ i){
		lg2[i] = lg2[i / 2] + 1;
	}
}
 
int main(){
	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
	init();
	std::cin >> N;
	for(int i = 1; i <= N; ++ i){
		std::cin >> h[i];
		sparse[i][0] = {h[i], i};
	}
	for(int l = 1; l < MAXL; ++ l){
		for(int i = 1; i + (1 << l) - 1 <= N; ++ i){
			sparse[i][l] = my_min(sparse[i][l - 1], sparse[i + (1 << (l - 1))][l - 1]);
		}
	}
	for(int i = 1; i <= N; ++ i){
		std::cin >> w[i];
		prefw[i] = prefw[i - 1] + w[i];
	}
	std::cout << rec() << endl;
}
/**
 
*/

Compilation message (stderr)

fancyfence.cpp: In function 'long long int rec(int, int)':
fancyfence.cpp:55:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |   auto [myh, myid] = get(id, r);
      |        ^

• 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