Submission #1046176

#TimeUsernameProblemLanguageResultExecution timeMemory
1046176ByeWorldFancy Fence (CEOI20_fancyfence)C++14
100 / 100
64 ms24360 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define int long long #define ll long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> ipii; typedef pair<ld,ld> pll; const int MAXN = 3e5+15; const int INF = 3e18+10; const int MX = 2e18; const int MOD = 1e9+7; void chmn(int &a, int b){ a = min(a, b); } void chsum(int &a, int b){ a%=MOD; b%=MOD; a = (a+b)%MOD; } void chmul(int &a, int b){ a%=MOD; b%=MOD; a = (a*b)%MOD; } int mul(int a, int b){ a%=MOD; b%=MOD; return (a*b)%MOD; } int sum(int a, int b){ a%=MOD; b%=MOD; return (a+b)%MOD; } int expo(int a, int b){ if(b==0) return 1; int te = expo(a, b/2); te = mul(te, te); return (b%2 ? mul(te, a) : te); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n; int h[MAXN], w[MAXN], pr[MAXN]; int two; struct seg { pii st[4*MAXN]; void bd(int id,int l, int r){ if(l==r){ st[id] = pii(h[l], l); return; } bd(lf, l, md); bd(rg, md+1, r); st[id] = min(st[lf], st[rg]); } pii que(int id, int l, int r, int x, int y){ if(x<=l && r<=y) return st[id]; if(r<x || y<l) return pii(INF, INF); return min(que(lf,l,md,x,y), que(rg,md+1,r,x,y)); } } A; int get(int x, int y){ return pr[y]-pr[x-1]; } int CNT(int x, int y, int h){ // x kiri kanan, y atas bawah, h blocks di bwh int X = mul(mul(x, x+1), two); int Y = mul(mul(y, y+1), two); chsum(Y, mul(h, y)); return mul(X, Y); } int ans; void solve(int l, int r, int las){ // las height if(l>r) return; int mn = A.que(1,1,n,l,r).se, val = A.que(1,1,n,l,r).fi; chsum(ans, CNT(get(l, r), val-las, las)); solve(l, mn-1, val); solve(mn+1, r, val); } signed main(){ // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; two = expo(2, MOD-2); for(int i=1; i<=n; i++) cin >> h[i]; A.bd(1, 1, n); for(int i=1; i<=n; i++){ cin >> w[i]; pr[i] = pr[i-1]+w[i]; } solve(1, n, 0); cout << ans << '\n'; } /* 2 2 2 2 2 //30 */
#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...