Submission #1106830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106830		sinataghizadeh	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	72 ms	11120 KiB

fancyfence

#include <bits/stdc++.h>
using namespace std;


typedef long long       ll;
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pll;
#define all(x)			(x).begin(),(x).end()
#define pb    			push_back
#define fi              first
#define se              second
#define mp make_pair
#define beg             begin
#define siz              size()
#define fastio          cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
#define endl       		'\n'
#define ins             insert
#define log             LOG
const ll inf = 1e18;
const ll mod = 1e9+7;
const int maxn=1e6+44;
const int log=24;
const int delta=229939;
ll n;

int main(){
	fastio
    cin>>n;
    vector<ll>prefix(n+1);
    vector<ll>H(n+1),W(n+1);
    ll res=0;
    for(ll i=1;i<=n;i++) {
        cin>>H[i];
    }
    for(ll i=1;i<=n;i++) {
        cin>>W[i];
        prefix[i]=prefix[i-1]+W[i];
    }
   vector<pair<ll,ll>>v(n);
   set<ll>s;
   for(ll i=1;i<=n;i++) {
    s.insert(i);
    v[i-1]=mp(H[i],i);
   }
   sort(v.rbegin(),v.rend());
   s.insert(0);
   s.insert(n+1);
   for(ll t=0;t<n;t++) {
        ll index=v[t].second;
        s.erase(index);
        auto it= s.upper_bound(index);
        ll wd = prefix[*it-1]-prefix[index];
        it=prev(it,1);
        ll ws = prefix[index-1]-prefix[*it];
        wd%=mod;
        ws%=mod;
        ll w = W[index];
        ll h = H[index];
        ll sum=h*(h+(ll)1)/(ll)2;
        ll sumw=w*(w+(ll)1)/(ll)2;
        sum%=mod;
        sumw%=mod;
        ll toadd=0;
        toadd+=(ws*w)%mod;
        toadd%=mod;
        toadd+=(wd*w)%mod;
        toadd%=mod;
        toadd+=(wd*ws)%mod;toadd%=mod;
        toadd+=sumw;toadd%=mod;
        toadd*=sum;toadd%=mod;
        res+=toadd;
        res%=mod;
   }    
	cout<<res;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27