Submission #1029885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029885		hengliao	Flooding Wall (BOI24_wall)	C++17	70 / 100	5098 ms	41328 KiB

Main

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

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=5e5+5;
const ll mod=1e9+7;

ll pw[mxN];

struct segtree{
    vll tree, lazy;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcount(treelen)!=1){
            treelen++;
        }
        tree.resize(2*treelen);
        lazy.resize(2*treelen);
    }

    void push(ll idx, ll low, ll high){
        if(low!=high){
            lazy[2*idx]+=lazy[idx];
            lazy[2*idx+1]+=lazy[idx];
        }
    }

    void check(ll idx, ll low, ll high){
        tree[idx]+=lazy[idx];
        push(idx, low, high);
        lazy[idx]=0;
    }

    void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            lazy[idx]+=val;
            check(idx, low, high);
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update1(2*idx, low, mid, qlow, qhigh, val);
        update1(2*idx+1, mid+1, high, qlow, qhigh, val);
        tree[idx]=max(tree[2*idx], tree[2*idx+1]);
    }

    ll getmax1(ll idx, ll low, ll high, ll qlow, ll qhigh){
        check(idx, low, high);
        if(low>=qlow && high<=qhigh){
            return tree[idx];
        }
        if(low>qhigh || high<qlow){
            return 0LL;
        }
        ll mid=(low+high)/2;
        return max(getmax1(2*idx, low, mid, qlow, qhigh), 
        getmax1(2*idx+1, mid+1, high, qlow, qhigh));
    }

    void update(ll qlow, ll qhigh, ll val){
        update1(1, 0, treelen-1, qlow, qhigh, val);
    }

    ll getmax(ll qlow, ll qhigh){
        return getmax1(1, 0, treelen-1, qlow, qhigh);
    }

    ll bs(ll idx, ll low, ll high, ll val){
        check(idx, low, high);
        if(low==high){
            return low;
        }
        ll mid=(low+high)/2;
        check(2*idx, low, mid);
        if(tree[2*idx]>=val){
            return bs(2*idx, low, mid, val);
        }
        else{
            return bs(2*idx+1, mid+1, high, val);
        }
    }
};

void solve(){
	ll n;
	cin>>n;
	vector<pll> a(n);
	for(auto &[x, y]:a){
		cin>>x;
	}
	for(auto &[x, y]:a){
		cin>>y;
	}
	for(auto &[x, y]:a){
		if(x>y){
			swap(x, y);
		}
	}
	vll h;
	for(auto &[x, y]:a){
		h.pb(x);
		h.pb(y);
	}
	sort(h.begin(), h.end());
	h.erase(unique(h.begin(), h.end()), h.end());
	vll pre(n+1);
	vll suf(n+2);
	vll val(n);
	ll ans=0;
	ll pr=0;
	ll sum=0;
	ll tep=0;
	for(auto &cur:h){
		pre[0]=1;
		for(ll i=0;i<n;i++){
			val[i]=0;
			if(a[i].F<cur){
				val[i]++;
			}
			if(a[i].S<cur){
				val[i]++;
			}
		}
		pre[0]=1;
		for(ll i=0;i<n;i++){
			pre[i+1]=pre[i]*val[i];
			pre[i+1]%=mod;
		}
		suf[n+1]=1;
		for(ll i=n-1;i>=0;i--){
			suf[i+1]=suf[i+2]*val[i];
			suf[i+1]%=mod;
		}
		sum=0;
		for(ll i=0;i<n;i++){
			tep=val[i];
			tep*=pw[i]-pre[i]+mod;
			tep%=mod;
			tep*=pw[n-i-1]-suf[i+2]+mod;
			tep%=mod;
			sum+=tep;
			sum%=mod;
		}
		ans+=sum*(cur-pr);
		ans%=mod;
		pr=cur;
	}
	cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

	pw[0]=1;
	for(ll i=1;i<mxN;i++){
		pw[i]=pw[i-1]*2;
		pw[i]%=mod;
	}

	solve();
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 17 / 17
• Subtask 3: 19 / 19
• Subtask 4: 14 / 14
• Subtask 5: 12 / 12
• Subtask 6: 0 / 30