Submission #1147977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147977		Dan4Life	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	72 ms	5540 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)

using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;

const int mxN = (int)1e5+10;
const ll MOD = (ll)1e9+7;
ll n, x;
ll h[mxN], pr[mxN];
vector<array<ll,2>> v;

ll pick12(ll x){ x%=MOD; return (x*(x+1)/2)%MOD; }

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n; ll ans = 0; set<pair<ll,ll>> S;
	for(int i = 0; i < n; i++) cin >> h[i];
	for(int i = 0; i < n; i++){
		cin >> x, v.pb({h[i],x});
		pr[i+1] = (pr[i]+x)%MOD;
	}
	vi ind(n,0); iota(all(ind),0); 
	sort(all(ind),[&](int i, int j){ return h[i]>h[j]; });
	for(auto i : ind){
		auto it = S.lower_bound({i,-1});
		auto it2 = S.lower_bound({i,-1});
		bool le = 0, ri = 0; ll H = h[i];
		if(it!=begin(S)) it--,le=(it->second==i-1);
		if(it2!=end(S)) ri=(it2->first==i+1);
		
		int nL=i, nR=i;
		if(le) nL = it->first;
		if(ri) nR = it2->second;
		
		if(ri){
			ll totW = (pr[nR+1]-pr[i+1]+MOD)%MOD;
			S.erase(*it2);
			ans-=(pick12(totW)*pick12(H))%MOD;
			ans+=MOD; ans%=MOD;
		}
		if(le){
			ll totW = (pr[i]-pr[nL]+MOD)%MOD;
			S.erase(*it);
			ans-=(pick12(totW)*pick12(H))%MOD;
			ans+=MOD; ans%=MOD;
		}
		ll totW = (pr[nR+1]-pr[nL]+MOD)%MOD;
		S.insert({nL,nR});
		ans+=(pick12(totW)*pick12(H))%MOD;
		ans%=MOD;
	}
	cout << ans << "\n";
}

• 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