Submission #1019347

#TimeUsernameProblemLanguageResultExecution timeMemory
1019347DobromirAngelovFancy Fence (CEOI20_fancyfence)C++14
0 / 100
1 ms652 KiB
#include<bits/stdc++.h> #define endl '\n' #define fi first #define se second #define int long long using namespace std; const int MAXN=1e5+5; const int MOD=1e9+7; int n; int h[MAXN]; int w[MAXN]; long long pref[MAXN]; int ord[MAXN]; bool used[MAXN]; vector<pair<int,int> > ev; pair<int,int> rng[MAXN]; int ans=0; int rect(long long w,long long h) { w%=MOD; h%=MOD; return ((w*(w+1)/2)%MOD*(h*(h+1)/2)%MOD)%MOD; } void sum(int &a,int val) { a+=val; if(a>=MOD) a-=MOD; } void subtr(int &a,int val) { a-=val; if(a<0) a+=MOD; } void addL(int ind) { ev.push_back({rng[ind-1].fi, ind}); long long d=pref[ind-1]-pref[rng[ind-1].fi-1]; subtr(ans, rect(d,h[ind])); } void changeRngL(int ind) { int l=rng[ind-1].fi; int r=rng[ind].se; rng[l]={rng[l].fi, rng[r].se}; rng[r]={rng[l].fi, rng[r].se}; } void addR(int ind) { ev.push_back({ind, rng[ind+1].se}); long long d=pref[rng[ind+1].se]-pref[ind]; subtr(ans, rect(d,h[ind])); } void changeRngR(int ind) { int l=rng[ind].fi; int r=rng[ind+1].se; rng[l]={rng[l].fi, rng[r].se}; rng[r]={rng[l].fi, rng[r].se}; } void calc(int h) { for(auto cur: ev) {//cout<<"("<<cur.fi<<","<<cur.se<<") "; long long d=pref[cur.se]-pref[cur.fi-1]; sum(ans, rect(d,h)); cout<<1/0<<endl; } ev.clear(); //cout<<ans<<endl; } bool cmp(int x,int y) { if(h[x]==h[y]) return x<y; return h[x]>h[y]; } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n; for(int i=1;i<=n;i++) cin>>h[i]; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) pref[i]=pref[i-1]+w[i]; for(int i=1;i<=n;i++) rng[i]={i,i}; iota(ord,ord+n,1); sort(ord,ord+n,cmp); for(int i=0;i<n;i++) { if(i>0 && h[ord[i]]<h[ord[i-1]]) calc(h[ord[i-1]]); int ind=ord[i]; pair<int,int> last({-1,-1}); if(!ev.empty()) last=ev.back(); if(used[ind-1]) {//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl; if(ind-1==last.se) last.se++, ev.back().se++; else addL(ind); changeRngL(ind); //cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl; } if(ev.size()>0) last=ev.back(); if(used[ind+1]) {//cout<<i<<" "<<ind<<" "<<last.fi<<" "<<last.se<<endl; if(last.se==ind) { last.se=rng[ind+1].se; ev.back().se=rng[ind+1].se; long long d=pref[rng[ind+1].se]-pref[ind]; subtr(ans, rect(d,h[ind])); } else addR(ind); changeRngR(ind); //cout<<ans<<" "<<rng[ind].fi<<" "<<rng[ind].se<<endl; } if(!used[ind-1] && !used[ind+1]) sum(ans, rect(w[ind], h[ind])); used[ind]=1; //cout<<i<<" "<<ord[i]<<": "<<ans<<endl; } calc(h[ord[n-1]]); cout<<ans<<endl; return 0; } /* 6 1 3 5 3 2 6 1 1 1 1 1 1 5 1 3 5 3 2 3 2 1 3 3 7 3 4 1 9 8 3 9 1 1 1 1 1 1 1 10 4 4 4 4 4 4 4 4 4 4 1 3 7 8 4 5 9 2 7 5 17 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 3 9 5 7 3 8 1 9 9 6 1 2 4 8 5 4 */

Compilation message (stderr)

fancyfence.cpp: In function 'void calc(long long int)':
fancyfence.cpp:77:16: warning: division by zero [-Wdiv-by-zero]
   77 |         cout<<1/0<<endl;
      |               ~^~
#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...