Submission #577548

#TimeUsernameProblemLanguageResultExecution timeMemory
577548juggernautFancy Fence (CEOI20_fancyfence)C++14
100 / 100
68 ms18608 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif int h[100005]; int w[100005]; ll pref[100005]; int n; ll mod=1e9+7; const ll cn=(mod+1)/2; pair<int,int>sp[100005][17]; int logs[100005]; int get(int l,int r){ int len=logs[r-l+1]; return min(sp[l][len],sp[r-(1<<len)+1][len]).sc; } ll ans; void go(int l,int r){ if(l>r)return; int pos=get(l,r); ll A=w[pos]; ll B=h[pos]; ans+=A*(A+1)/2%mod*((B*(B+1)/2)%mod)%mod; ans%=mod; B=B*(B+1)/2%mod; ans+=B*((pref[pos-1]-pref[l-1])%mod)%mod*((pref[r]-pref[pos])%mod)%mod; ans%=mod; ans+=B*A%mod*((pref[r]-pref[l-1]-A)%mod)%mod; ans%=mod; go(l,pos-1); go(pos+1,r); } int main(){ scanf("%d",&n); logs[0]--; for(int i=1;i<=n;i++){ scanf("%d",&h[i]); logs[i]=logs[i>>1]+1; sp[i][0]=make_pair(h[i],i); } for(int j=1;j<17;j++) for(int i=1;i+(1<<j)-1<=n;i++)sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]); for(int i=1;i<=n;i++){ scanf("%d",&w[i]); pref[i]=pref[i-1]; pref[i]+=w[i]; } go(1,n); cout<<ans; }

Compilation message (stderr)

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fancyfence.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d",&h[i]);
      |   ~~~~~^~~~~~~~~~~~
fancyfence.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d",&w[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...