Submission #534912

#TimeUsernameProblemLanguageResultExecution timeMemory
534912vectorFancy Fence (CEOI20_fancyfence)C++17
100 / 100
155 ms38272 KiB
#include<bits/stdc++.h> #define MOD 1000000007 #define SIZE 100010 using namespace std; typedef long long ll; struct st1 { ll l,r; }; struct st2 { ll h,w,idx; }; ll N,psum[SIZE],ans,seg2[SIZE<<2],lz[SIZE<<2]; st1 sparse[SIZE][17]; st2 A[SIZE]; vector<st2>v; void push(ll l,ll r,ll node) { if(lz[node]==0)return; seg2[node]=lz[node]; if(l^r)lz[node<<1]=lz[node<<1|1]=lz[node]; lz[node]=0; } void upd(ll l,ll r,ll node,ll s,ll e,ll x) { push(l,r,node); if(l>e||r<s)return; if(s<=l&&r<=e){ lz[node]=x; push(l,r,node); return; } ll mid=l+r>>1; upd(l,mid,node<<1,s,e,x); upd(mid+1,r,node<<1|1,s,e,x); } ll que(ll l,ll r,ll node,ll s) { push(l,r,node); if(l>s||r<s)return 0; if(l==s&&r==s)return seg2[node]; ll mid=l+r>>1; return max(que(l,mid,node<<1,s),que(mid+1,r,node<<1|1,s)); } bool comp(st2 x,st2 y) { return x.h<y.h; } ll S(ll x) { x%=MOD; return (x*(x+1)/2)%MOD; } int main() { ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>N; for(int i=1;i<=N;i++)cin>>A[i].h; for(int i=1;i<=N;i++)cin>>A[i].w; bool f=false; st2 temp={0,0,0}; v.push_back(temp); for(int i=1;i<=N;i++){ if(f){ if(temp.h==A[i].h)temp.w+=A[i].w; else{ v.push_back(temp); f=false; } } if(!f){ temp.h=A[i].h; temp.w=A[i].w; f=true; } } v.push_back(temp); N=v.size()-1; temp={0,MOD,N+1}; v.push_back(temp); for(ll i=1;i<=N;i++){ v[i].idx=i; //printf("[%lld %lld %lld]\n",v[i].h,v[i].w,v[i].idx); psum[i]=psum[i-1]+v[i].w; } for(ll i=1;i<=N;i++){ sparse[i][0].r=v[i+1].h; sparse[i][0].l=v[i-1].h; //printf("[%lld %lld] ",sparse[i][0].l,sparse[i][0].r); } //printf("\n"); for(ll j=1;j<17;j++){ for(ll i=1;i<=N;i++){ sparse[i][j].r=min(sparse[i][j-1].r,sparse[min(N,i+(1<<(j-1)))][j-1].r); sparse[i][j].l=min(sparse[i][j-1].l,sparse[max(1ll,i-(1<<(j-1)))][j-1].l); //printf("[%lld %lld] ",sparse[i][j].l,sparse[i][j].r); } //printf("\n"); } sort(v.begin(),v.end()-1,comp); for(ll j=1;j<=N;j++){ ll i=v[j].idx; ll l=1,r=i,mid,a,b,mx,x=i; for(ll k=16;k>=0;k--)if(sparse[x][k].r>=v[j].h)x=min(N,x+(1<<k)); b=x; x=i; for(ll k=16;k>=0;k--)if(sparse[x][k].l>=v[j].h)x=max(1ll,x-(1<<k)); a=x; mx=que(1,N,1,i); upd(1,N,1,a,b,v[j].h); //printf("%lld %lld %lld %lld %lld\n",a,b,i,v[j].h,mx); ans=(ans+S(psum[b]-psum[a-1])*(S(v[j].h)-S(mx)+MOD))%MOD; //printf("%lld\n",ans); } cout<<ans; }

Compilation message (stderr)

fancyfence.cpp: In function 'void upd(ll, ll, ll, ll, ll, ll)':
fancyfence.cpp:34:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     ll mid=l+r>>1;
      |            ~^~
fancyfence.cpp: In function 'll que(ll, ll, ll, ll)':
fancyfence.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     ll mid=l+r>>1;
      |            ~^~
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:104:12: warning: unused variable 'l' [-Wunused-variable]
  104 |         ll l=1,r=i,mid,a,b,mx,x=i;
      |            ^
fancyfence.cpp:104:16: warning: unused variable 'r' [-Wunused-variable]
  104 |         ll l=1,r=i,mid,a,b,mx,x=i;
      |                ^
fancyfence.cpp:104:20: warning: unused variable 'mid' [-Wunused-variable]
  104 |         ll l=1,r=i,mid,a,b,mx,x=i;
      |                    ^~~
#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...