Submission #1289530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289530		liangjeremy	Fancy Fence (CEOI20_fancyfence)	C++20	30 / 100	1095 ms	6980 KiB

fancyfence

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
//using namespace __gnu_pbds;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<int mod, int RT>struct mint{
	int v;
	static constexpr mint rt(){ return RT; }
	explicit operator int() const { return v; }
	mint():v(0){}
	mint(int _v):v((int)(_v%mod)){ v+=(v<0)*mod; }
	mint& operator+=(mint o){
		if((v+=o.v)>=mod)v-=mod;
		return *this;
	}
	mint& operator-=(mint o){
		if((v-=o.v)<0)v+=mod;
		return *this; 
	}
	mint& operator*=(mint o){
		v=(int)((int)(v*o.v%mod));
		return *this; 
	}
	mint& operator/=(mint o){
		*this*=inv(o);
		return *this;  
	}
	friend mint mpow(mint a, int x){
		if(x==0)return 1;
    	mint t=mpow(a,x>>1);
    	if(x%2==0)return t*t;
    	return t*t*a;
	}
	friend mint inv(mint a){
		return mpow(a,mod-2); 
	}
	friend mint operator+(mint a, mint b){ return a+=b; }
	friend mint operator-(mint a, mint b){ return a-=b; }
	friend mint operator*(mint a, mint b){ return a*=b; }
	friend mint operator/(mint a, mint b){ return a/=b; }
	mint operator-() const { return mint(-v); }
	mint& operator++() { return *this+=1; }
	mint& operator--() { return *this-=1; }
	bool operator==(const mint& o) const { return v==o.v; }
	bool operator!=(const mint& o) const { return v!=o.v; }
}; using mi=mint<(int)1e9+7,5>;

class SparseTable{
    private:
        int n,log2dist; vector<vector<int>>st;
    public:
        SparseTable(vector<int> &v){
            n=(int)(v.size());
            log2dist=1+(int)(log2(n));
            st.resize(log2dist);
            st[0]=v;
            for(int i=1; i<log2dist; i++){
                st[i].resize(n-(1<<i)+1);
                for(int j=0; j<n-(1<<i)+1; j++){
                    st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
                }
            }
        } 
        int query(int l, int r){
            int i=(ll)log2(r-l+1);
            return min(st[i][l],st[i][r-(1<<i)+1]);
        }
};

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    int n; cin>>n; vector<int>h(n+1); vector<int>w(n+1);
    for(int i=1; i<=n; i++){ cin>>h[i]; }
    for(int i=1; i<=n; i++){ cin>>w[i]; }
    SparseTable st(h); mi ans=0; 
    for(int i=1; i<=n; i++){
    	mi hh=h[i]; mi ww=w[i]; ans+=hh*(hh+1)*ww*(ww+1)/4; 
    }
    for(int i=1; i<=n; i++){
    	for(int j=i+1; j<=n; j++){
    		mi l=w[i]; mi r=w[j]; mi hh=st.query(i,j); ans+=l*r*hh*(hh+1)/2; 
    	}
    }
    cout<<(int)ans<<'\n'; 
}
/*
Overhead the albatross hangs motionless upon the air
And deep beneath the rolling waves in labyrinths of coral caves
The echo of a distant time comes willowing across the sand
And everything is green and submarine

And no one showed us to the land
And no one knows the wheres or whys
But something stirs and something tries
And starts to climb towards the light
*/

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