Submission #395161

#TimeUsernameProblemLanguageResultExecution timeMemory
395161Pichon5Fancy Fence (CEOI20_fancyfence)C++17
100 / 100
115 ms5652 KiB
#include<bits/stdc++.h> #define lcm(a,b) (a/__gcd(a,b))*b #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define ll long long int #define vi vector<int> #define vll vector<ll> #define pb push_back #define F first #define S second #define mp make_pair //salida rapida "\n" //DECIMALES fixed<<sp(n)<<x<<endl; //gcd(a,b)= ax + by //lCB x&-x //set.erase(it) - ersases the element present at the required index//auto it = s.find(element) //set.find(element) - iterator pointing to the given element if it is present else return pointer pointing to set.end() //set.lower_bound(element) - iterator pointing to element greater than or equal to the given element //set.upper_bound(element) - iterator pointing to element greater than the given element // | ^ //__builtin_popcount(x) using namespace std; const ll MOD=1e9+7; vll h,w; ll res=0; vi ind; vector<bool>vis; int P[1000005]; ll bin(ll x){ x%=MOD; return ((x*(x+1))/2)%MOD; } ll T(ll x,ll y){ return (bin(x)%MOD*bin(y)%MOD)%MOD; } bool comp(int x,int y){ return h[x]>h[y]; } int _find(int x){ if(P[x]==x)return x; return P[x]=_find(P[x]); } void _union(int x,int y){ x=_find(x),y=_find(y); if(x==y)return; P[x]=y; w[y]=(w[y]+w[x])%MOD; } int sum(int x){ x=_find(x); return w[x]; } int main() { //freopen("input1.txt","r",stdin); ll n,x; cin>>n;vis.assign(n+1,false); for(int i=0;i<n;i++){ P[i]=i; cin>>x; h.pb(x); } for(int i=0;i<n;i++){ cin>>x;ind.pb(i); w.pb(x); } ll res=0; sort(ind.begin(),ind.end(),comp); for(int i=0;i<n;i++){ int it=ind[i],L=0,R=0; vis[it]=true; //siempre me "conecto" con uno de mayor o igual altitud if(it && vis[it-1]){ L=sum(it-1); _union(it,it-1); } if(it<n-1 && vis[it+1]){ R=sum(it+1); //cout<<"padre "<<_find(it+1)<<endl; _union(it,it+1); } //cout<<L<<" " <<R<<endl; int SUM=(L+R+w[it])%MOD; res=(res+T(SUM,h[it])+MOD)%MOD; res=(res-T(L,h[it])+MOD)%MOD; res=(res-T(R,h[it])+MOD)%MOD; } res+=MOD; res%=MOD; cout<<res<<endl; return 0; } //409336628
#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...